結果
問題 | No.1572 XI |
ユーザー |
![]() |
提出日時 | 2021-06-27 13:43:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 461 ms / 2,000 ms |
コード長 | 1,328 bytes |
コンパイル時間 | 3,425 ms |
コンパイル使用メモリ | 206,144 KB |
最終ジャッジ日時 | 2025-01-22 14:06:08 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>int main() {using namespace std;cin.tie(nullptr)->sync_with_stdio(false);int h, w;cin >> h >> w;int si, sj;cin >> si >> sj;--si, --sj;int ti, tj;cin >> ti >> tj;--ti, --tj;vector<string> s(h);for (auto&& e : s) cin >> e;constexpr array di{1, 0, -1, 0};constexpr array dj{0, 1, 0, -1};array<array<int, 4>, 6> get_nk;get_nk[0] = {1, 2, 3, 4};get_nk[1] = {5, 1, 0, 1};get_nk[2] = {2, 5, 2, 0};get_nk[3] = {0, 3, 5, 3};get_nk[4] = {4, 0, 4, 5};get_nk[5] = {3, 4, 1, 2};vector dist(h, vector<array<int, 6>>(w));for (int i = 0; i < h; ++i)for (int j = 0; j < w; ++j) dist[i][j].fill(-1);vector<tuple<int, int, int>> que{{si, sj, 0}};dist[si][sj][0] = 0;for (int z = 0; z < int(size(que)); ++z) {auto [i, j, k] = que[z];if (i == ti and j == tj and k == 0) {cout << dist[i][j][k] << '\n';exit(0);}for (int d : {0, 1, 2, 3}) {int ni = i + di[d];int nj = j + dj[d];if (ni < 0 or ni >= h or nj < 0 or nj >= w or s[ni][nj] == '#') continue;int nk = get_nk[k][d];if (dist[ni][nj][nk] == -1) {dist[ni][nj][nk] = dist[i][j][k] + 1;que.emplace_back(ni, nj, nk);}}}cout << "-1\n";}