結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2017-03-26 14:19:11 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 1,580 ms |
コンパイル使用メモリ | 165,340 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 07:14:08 |
合計ジャッジ時間 | 2,148 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define INF 2000000000#define MOD 1000000007typedef long long ll;typedef pair<int, int> P;int main(){int h, w;cin >> h >> w;int sx, sy, gx, gy;cin >> sx >> sy >> gx >> gy;string b[h+1];for (int i = 1; i <= h; i++) {cin >> b[i];}bool rec[h+1][w+1];for (int i = 0; i <= h; i++) {for (int j = 0; j <= w; j++) {rec[i][j] = false;}}// startqueue<P> q;q.push(P(sx,sy));while (true) {if (q.empty()) {cout << "NO" << "\n";return 0;}P tmp = q.front(); q.pop();int x = tmp.first;int y = tmp.second;if (x==gx&&y==gy) {cout << "YES" << "\n";return 0;}// cout << "debug " << x << " " << y << "\n";if (rec[x][y]) {continue;}if (x-1>=1&&abs((b[x][y-1]-'0')-(b[x-1][y-1]-'0'))<=1) {q.push(P(x-1,y));}if (y-1>=1&&abs((b[x][y-1]-'0')-(b[x][y-1-1]-'0'))<=1) {q.push(P(x,y-1));}if (x+1<=h&&abs((b[x][y-1]-'0')-(b[x+1][y-1]-'0'))<=1) {q.push(P(x+1,y));}if (y+1<=w&&abs((b[x][y-1]-'0')-(b[x][y+1-1]-'0'))<=1) {q.push(P(x,y+1));}if (x-2>=1&&(b[x][y-1]==b[x-2][y-1])&&(b[x-1][y-1]-'0')<=(b[x-2][y-1]-'0')) {q.push(P(x-2,y));}if (y-2>=1&&(b[x][y-1]==b[x][y-2-1])&&(b[x][y-1-1]-'0')<=(b[x][y-2-1]-'0')) {q.push(P(x,y-2));}if (x+2<=h&&(b[x][y-1]==b[x+2][y-1])&&(b[x+1][y-1]-'0')<=(b[x][y-1]-'0')) {q.push(P(x+2,y));}if (y+2<=w&&(b[x][y-1]==b[x][y+2-1])&&(b[x][y+1-1]-'0')<=(b[x][y+2-1]-'0')) {q.push(P(x,y+2));}rec[x][y] = true;}}