結果
問題 | No.424 立体迷路 |
ユーザー | zuvizudar |
提出日時 | 2017-06-14 22:26:15 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,502 bytes |
コンパイル時間 | 793 ms |
コンパイル使用メモリ | 97,676 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 07:14:21 |
合計ジャッジ時間 | 1,596 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
ソースコード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> using namespace std; #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define F(i,j,k) fill(i[0],i[0]+j*j,k) #define P(p) cout<<(p)<<endl; #define EXIST(s,e) ((s).find(e)!=(s).end()) #define INF 1<<25 #define pb push_back #define debug cout<<"!!!"<<endl; typedef vector<int> vi; typedef vector<long long> vl; typedef vector<double> vd; typedef pair<int,int> pii; typedef pair<long,long> pll; typedef long long ll; /* 合わないので写経いたしました。 char s[50][50]={}; int a[50][50]={}; int h,w,sx,sy,gx,gy; #ifdef gomi void dfs(int p,int q){ //x,y if(cnt[q][p]==1) //探索済みなら return; cnt[q][p]++; if(p>0&&abs(meiro[q][p-1]-meiro[q][p])<=1)//左上下 dfs(p-1,q); if(p<w-1&&abs(meiro[q][p+1]-meiro[q][p])<=1)//右上下 dfs(p+1,q); if(q<h-1&&abs(meiro[q+1][p]-meiro[q][p])<=1)//前上下 dfs(p,q+1); if(q>0&&abs(meiro[q-1][p]-meiro[q][p])<=1)//後上下 dfs(p,q-1); if(p>1&&meiro[q][p]==meiro[q][p-2]&&meiro[q][p]>meiro[q][p-1]){//1つ飛ばして左 dfs(p-2,q); debug } if(p<w-2&&meiro[q][p]==meiro[q][p+2]&&meiro[q][p]>meiro[q][p+1])//1つ飛ばして右 dfs(p+2,q); if(q<h-2&&meiro[q][p]==meiro[q+2][p]&&meiro[q][p]>meiro[q+1][p])//1つ飛ばして前 dfs(p,q+2); if(q>1&&meiro[q][p]==meiro[q-2][p]&&meiro[q][p]>meiro[q-1][p])//1つ飛ばして後 dfs(p,q-2); } #endif void f(int p,int q){ if(!a[p][q]){ a[p][q]++; //はしごを縦に使う場合 if(p>0 &&abs(s[p-1][q]-s[p][q])<2)f(p-1,q); if(p<h-1&&abs(s[p+1][q]-s[p][q])<2)f(p+1,q); if(q>0 &&abs(s[p][q-1]-s[p][q])<2)f(p,q-1); if(q<w-1&&abs(s[p][q+1]-s[p][q])<2)f(p,q+1); //はしごを横に使う場合 if(p>1 &&s[p-2][q]==s[p][q]&&s[p][q]>s[p-1][q])f(p-2,q); if(p<h-2&&s[p+2][q]==s[p][q]&&s[p][q]>s[p+1][q])f(p+2,q); if(q>1 &&s[p][q-2]==s[p][q]&&s[p][q]>s[p][q-1])f(p,q-2); if(q<w-2&&s[p][q+2]==s[p][q]&&s[p][q]>s[p][q+1])f(p,q+2); } } int main(){ cin>>h>>w; cin>>sx>>sy>>gx>>gy; sx--;sy--;gx--;gy--; for(int y=0;y<h;y++){ #ifdef gomi for(int x=0;x<w;x++){ char tmp; cin>>tmp; s[y][x]=tmp-'0'; } #endif cin>>s[y]; } f(sx,sy); if(a[gy][gx]==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } */ char s[99][99]; int a[99][99],h,w; //(x,y)に到達可能かをa[x][y]に保存 void f(int p,int q){ if(!a[p][q]){ a[p][q]++; //はしごを縦に使う場合 if(p>0 &&abs(s[p-1][q]-s[p][q])<2)f(p-1,q); if(p<h-1&&abs(s[p+1][q]-s[p][q])<2)f(p+1,q); if(q>0 &&abs(s[p][q-1]-s[p][q])<2)f(p,q-1); if(q<w-1&&abs(s[p][q+1]-s[p][q])<2)f(p,q+1); //はしごを横に使う場合 if(p>1 &&s[p-2][q]==s[p][q]&&s[p][q]>s[p-1][q])f(p-2,q); if(p<h-2&&s[p+2][q]==s[p][q]&&s[p][q]>s[p+1][q])f(p+2,q); if(q>1 &&s[p][q-2]==s[p][q]&&s[p][q]>s[p][q-1])f(p,q-2); if(q<w-2&&s[p][q+2]==s[p][q]&&s[p][q]>s[p][q+1])f(p,q+2); } } int main(){ int sx,sy,gx,gy,i; scanf("%d%d%d%d%d%d ",&h,&w,&sx,&sy,&gx,&gy); //配列のindexは0-basedで、入力は1-basedなのでそろえる sx--;sy--;gx--;gy--; for(i=0;i<h;i++)//gets(s[i]); cin>>s[i]; f(sx,sy); puts(a[gx][gy]?"YES":"NO"); return 0; }