結果
問題 | No.2096 Rage With Our Friends |
ユーザー | SSRS |
提出日時 | 2022-10-07 22:10:04 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 652 ms / 5,000 ms |
コード長 | 3,225 bytes |
コンパイル時間 | 2,051 ms |
コンパイル使用メモリ | 184,308 KB |
実行使用メモリ | 178,568 KB |
最終ジャッジ日時 | 2023-09-03 12:52:48 |
合計ジャッジ時間 | 6,683 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 227 ms
73,804 KB |
testcase_12 | AC | 652 ms
178,568 KB |
testcase_13 | AC | 176 ms
73,556 KB |
testcase_14 | AC | 306 ms
73,620 KB |
testcase_15 | AC | 226 ms
73,616 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 213 ms
73,556 KB |
testcase_18 | AC | 1 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 371 ms
73,548 KB |
testcase_22 | AC | 379 ms
73,612 KB |
testcase_23 | AC | 20 ms
6,804 KB |
testcase_24 | AC | 231 ms
45,700 KB |
testcase_25 | AC | 138 ms
25,544 KB |
testcase_26 | AC | 82 ms
17,596 KB |
testcase_27 | AC | 80 ms
17,856 KB |
testcase_28 | AC | 3 ms
4,380 KB |
testcase_29 | AC | 40 ms
10,256 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1000000; int main(){ int H, W; cin >> H >> W; int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; sx--; sy--; gx--; gy--; vector<string> S(H); for (int i = 0; i < H; i++){ cin >> S[i]; } vector<int> mn(W, INF); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ if (S[i][j] == '.'){ mn[j] = min(mn[j], i); } } } vector<vector<int>> mx(H, vector<int>(W, -INF)); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ if (i > 0){ mx[i][j] = mx[i - 1][j]; } if (S[i][j] == '.'){ mx[i][j] = i; } } } vector<vector<vector<int>>> d(2, vector<vector<int>>(H, vector<int>(W, INF))); deque<tuple<int, int, int, int>> dq; dq.push_back(make_tuple(0, 0, sx, sy)); while (!dq.empty()){ int c = get<0>(dq.front()); int t = get<1>(dq.front()); int x = get<2>(dq.front()); int y = get<3>(dq.front()); dq.pop_front(); if (d[t][x][y] == INF){ d[t][x][y] = c; if (t == 0){ if (y > 0){ int m = mx[min(x + 1, H - 1)][y - 1]; if (m != -INF){ if (d[1][m][y - 1] == INF){ dq.push_front(make_tuple(c, 1, m, y - 1)); } int x2 = min(x + 1, H - 1); if (y > 1){ if (d[1][x2][y - 2] == INF){ dq.push_back(make_tuple(c + 1, 1, x2, y - 2)); } } if (d[1][x2][y] == INF){ dq.push_back(make_tuple(c + 1, 1, x2, y)); } int x3 = min(m + 1 + max(x - m, 0) / 2, H - 1); if (y > 1){ if (d[1][x3][y - 2] == INF){ dq.push_front(make_tuple(c, 1, x3, y - 2)); } } if (d[1][x3][y] == INF){ dq.push_front(make_tuple(c, 1, x3, y)); } } } if (y < W - 1){ int m = mx[min(x + 1, H - 1)][y + 1]; if (m != -INF){ if (d[1][m][y + 1] == INF){ dq.push_front(make_tuple(c, 1, m, y + 1)); } int x2 = min(x + 1, H - 1); if (y < W - 2){ if (d[1][x2][y + 2] == INF){ dq.push_back(make_tuple(c + 1, 1, x2, y + 2)); } } if (d[1][x2][y] == INF){ dq.push_back(make_tuple(c + 1, 1, x2, y)); } int x3 = min(m + 1 + max(x - m, 0) / 2, H - 1); if (y < W - 2){ if (d[1][x3][y + 2] == INF){ dq.push_front(make_tuple(c, 1, x3, y + 2)); } } if (d[1][x3][y] == INF){ dq.push_front(make_tuple(c, 1, x3, y)); } } } } if (t == 1){ if (S[x][y] == '.'){ if (d[0][x][y] == INF){ dq.push_front(make_tuple(c, 0, x, y)); } } if (x > 0){ if (d[1][x - 1][y] == INF){ dq.push_front(make_tuple(c, 1, x - 1, y)); } } } } } if (d[0][gx][gy] == INF){ cout << -1 << endl; } else { cout << d[0][gx][gy] << endl; } }