結果
問題 | No.424 立体迷路 |
ユーザー |
|
提出日時 | 2017-06-14 22:26:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#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 gomivoid dfs(int p,int q){ //x,yif(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);}#endifvoid 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 gomifor(int x=0;x<w;x++){char tmp;cin>>tmp;s[y][x]=tmp-'0';}#endifcin>>s[y];}f(sx,sy);if(a[gy][gx]==1)cout<<"YES"<<endl;elsecout<<"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;}