結果
問題 | No.424 立体迷路 |
ユーザー |
|
提出日時 | 2016-12-18 01:57:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,791 bytes |
コンパイル時間 | 1,043 ms |
コンパイル使用メモリ | 99,916 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 07:12:54 |
合計ジャッジ時間 | 1,513 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<vector>#include<string>#include<sstream>#include<iomanip>#include<utility>#include<cmath>#include<set>#include<list>#include<queue>#include<stack>#include<map>#include<cstring>using namespace std;typedef long long int ll;class disjointset{public:vector<int> rank;vector<int> p;void makeset(int x){p[x]=x;rank[x]=0;return;}disjointset(int s){rank.resize(s);p.resize(s);for(int i=0;i<s;i++)makeset(i);return;}int findset(int x){if(x!=p[x])p[x]=findset(p[x]);return p[x];}void link(int x,int y){if(rank[x]>rank[y])p[y]=x;else{p[x]=y;if(rank[x]==rank[y])rank[y]++;}return;}bool same(int x,int y){return findset(x)==findset(y);}void unite(int x,int y){link(findset(x),findset(y));return;}};string s[50];int h,w,sx,sy,gx,gy;disjointset d=disjointset(50*50);int dx[8]={1,-1,0,0,2,-2,0,0};int dy[8]={0,0,1,-1,0,0,2,-2};bool used[50][50]={};int toi(char a){stringstream ss;ss<<a;int ans;ss>>ans;return ans;}void dfs(int x,int y){used[x][y]=true;for(int r=0;r<8;r++){int tx=x+dx[r];int ty=y+dy[r];if(used[tx][ty])continue;if(tx<0||ty<0||tx>=h||ty>=w)continue;if(r<4){if(abs(toi(s[tx][ty])-toi(s[x][y]))<=1){d.unite(x*w+y,tx*w+ty);dfs(tx,ty);}}else{if(toi(s[tx][ty])==toi(s[x][y])){int a=toi(s[(tx+x)/2][(ty+y)/2]);if(a<=toi(s[x][y])){d.unite(x*w+y,tx*w+ty);dfs(tx,ty);}}}}return;}int main(){cin>>h>>w>>sx>>sy>>gx>>gy;sx--;sy--;gx--;gy--;for(int i=0;i<h;i++)cin>>s[i];dfs(sx,sy);if(d.same(sx*w+sy,gx*w+gy))cout<<"YES"<<endl;else cout<<"NO"<<endl;return 0;}