結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2016-09-22 23:32:39 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,547 bytes |
コンパイル時間 | 573 ms |
コンパイル使用メモリ | 69,824 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 07:06:17 |
合計ジャッジ時間 | 1,361 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <queue>#include <cmath>using namespace std;typedef pair<int, int> P;int MAZE[51][51];int w, h;int sx, sy, gx, gy;int d[51][51];int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };int bfs() {queue<P> que;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) d[i][j] = INT32_MAX;}que.push(P(sx, sy));d[sx][sy] = 0;while (que.size()) {P p = que.front(); que.pop();if (p.first == gx && p.second == gy) break;for (int i = 0; i < 4; i++) {int nx = p.first + dx[i], ny = p.second + dy[i];if (0 <= nx && nx < h && 0 <= ny && ny < w && abs(MAZE[nx][ny] - MAZE[p.first][p.second]) <= 1 && d[nx][ny] == INT32_MAX) {que.push(P(nx, ny));d[nx][ny] = d[p.first][p.second] + 1;}}for (int i = 0; i < 4; i++) {int nx = p.first + 2*dx[i], ny = p.second + 2*dy[i];if (0 <= nx && nx < h && 0 <= ny && ny < w && (MAZE[nx][ny] - MAZE[p.first][p.second]) == 0 && d[nx][ny] == INT32_MAX) {if ((nx == p.first && MAZE[nx][(ny + p.second) / 2] < MAZE[nx][ny]) || (ny == p.second && MAZE[(nx + p.first) / 2][ny] < MAZE[nx][ny])) {que.push(P(nx, ny));d[nx][ny] = d[p.first][p.second] + 1;}}}}return d[gx][gy];}int main(){cin >> h >> w >> sx >> sy >> gx >> gy;sx--; sy--; gx--; gy--;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {char c;cin >> c;MAZE[i][j] = c-'0';}}if (bfs() != INT32_MAX)cout << "YES" << endl;else cout << "NO" << endl;return 0;}