結果
問題 | No.424 立体迷路 |
ユーザー |
👑 |
提出日時 | 2020-03-05 21:56:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,609 bytes |
コンパイル時間 | 809 ms |
コンパイル使用メモリ | 75,152 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-14 02:09:43 |
合計ジャッジ時間 | 1,448 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include <iostream>#include <queue>using namespace std;struct dta{int x,y;};using ll = long long;using P = pair<int,int>;P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};char mp[50][50];bool lck[50][50];int main(){int h,w;cin>>h>>w;int sx,sy,gx,gy;cin>>sx>>sy>>gx>>gy;sx--;sy--;gx--;gy--;for(int i = 0; h > i; i++){for(int j = 0; w > j; j++){cin>>mp[i][j];}}queue<dta> a;a.push({sx,sy});lck[sx][sy] = true;while(!a.empty()){dta z = a.front();a.pop();if(z.x == gx && z.y == gy){cout << "YES" << endl;return 0;}//隣り合った高さのdistanceが1以下だったら通れるfor(int i = 0; 4 > i; i++){if(0 > z.x+ar4[i].first || z.x+ar4[i].first >= h || 0 > z.y+ar4[i].second || z.y+ar4[i].second >= w)continue;if(!lck[z.x+ar4[i].first][z.y+ar4[i].second] && abs(mp[z.x][z.y]-mp[z.x+ar4[i].first][z.y+ar4[i].second]) < 2){lck[z.x+ar4[i].first][z.y+ar4[i].second] = true;a.push({z.x+ar4[i].first,z.y+ar4[i].second});}}//同じ高さの2つ先のdistanceが0以下だったら通れるfor(int i = 0; 4 > i; i++){if(0 > z.x+ar4[i].first || z.x+ar4[i].first >= h || 0 > z.y+ar4[i].second || z.y+ar4[i].second >= w)continue;if(!lck[z.x+ar4[i].first*2][z.y+ar4[i].second*2] && abs(mp[z.x][z.y]-mp[z.x+ar4[i].first*2][z.y+ar4[i].second*2]) < 1 && mp[z.x][z.y] > mp[z.x+ar4[i].first][z.y+ar4[i].second]){lck[z.x+ar4[i].first*2][z.y+ar4[i].second*2] = true;a.push({z.x+ar4[i].first*2,z.y+ar4[i].second*2});}}}cout << "NO" << endl;}