問題はこちら
No.424 立体迷路 - yukicoder
標準的な迷路を解く問題にちょっとだけ条件が加わったもの。
素直なDFS/BFSで解ける。以下はDFS
char s[99][99];
int a[99][99],h,w;
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);
sx--;sy--;gx--;gy--;
for(i=0;i<h;i++)gets(s[i]);
f(sx,sy);
puts(a[gx][gy]?"YES":"NO");
return 0;
}
とりあえず縮めてみる。入力の受け取りを2-basedにすることで、添え字の範囲外チェックを省略する
またaをsをまとめる
char s[199][99];a,b;
f(p,q){s[p+98][q]++||();}
main(i,x,y){
for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[++i]+2););
f(a+1,b+1);
a=!puts(s[x+99][y+1]?"YES":"NO");
}
ということでメインの処理の部分をなんかいい感じにする必要がある
次に見る方向を(n,m)とすると（つまり(n,m)は(-1,0),(1,0),(0,-1),(0,1)のいずれか）
if(abs(s[p+n][q+m]-s[p][q])<2)f(p+n,q+m);
if(s[p+n+n][q+m+m]==s[p][q]&&s[p][q]>s[p+n][q+m])f(p+n+n,q+m+m);
と書くことができるので、この部分をdefineでまとめて
#define g(n,m)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m),
char s[199][99];
f(p,q,t){s[p+98][q]++||(g(-1,0)g(1,0)g(0,-1)g(0,1)1);}
main(i,a,b,x,y){
for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[++i]+2););
f(a+1,b+1);
n=!puts(s[x+99][y+1]?"YES":"NO");
}
そういえば、こういう風に回転して考えるのは以前にもやったことがあって、(n,m)→(m,-n)という風に値を更新していくことによってまとめることができる
#define g(n,m)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m),
f(p,q,t){s[p+98][q]++||(g(-1,0)g(1,0)g(0,-1)g(0,1)1);}
#define G,abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m),t=n,n=m,m=-t
f(p,q,t){s[p+98][q]++||(1 G G G G);}
同じ処理をするのにdefineをするのはあほらしいので、for文にまとめてしまいたい
f(p,q,t,T,n,m){n=1;m=0;if(s[p+98][q]++)for(T=0;T++<4;t=n,n=m,m=-t)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m));}
f(p,q,t,T,n,m){n=1;m=0;for(T=4*!s[p+99][q]++;T--;t=n,n=m,m=-t)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m);}
dfsの途中で自身を呼び出すことがあるので、これを次のようには書けない
for(;s[p+98][q]++<4;)
さらによく考えると、一度fを呼んだとき、その関数内で(n,m)→(m,-n)の変換がおこなわれる回数は0回か4回なので、n,mはグローバル変数にしてしまって問題ない
また、indexを2-basedではなく1-basedにすると、s[-1][*]にアクセスしてしまうことになるが、実際に提出してみるとエラーは起こらないらしい
ということでここまでをいったんまとめるとこうなる
char s[199][99];
n=1,m;
f(p,q,t,T){
for(T=4*!s[p+99][q]++;T--;t=n,n=m,m=-t)
abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),
s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m);
}
main(i,a,b,x,y){
for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[i++]+1););
f(a,b);
n=!puts(s[x+99][y]?"YES":"NO");
}
さらにfが短く書けないかを考える。隣のマスと2マス先との高さによって、はしごを縦横に使えるかを表にまとめると次のようになる。
|
2マス先が同じ高さ |
違う高さ |
| 隣のマスが2以上高い |
- |
- |
| 1高い |
縦 |
縦 |
| 同じ高さ |
縦 |
縦 |
| 1低い |
縦横 |
縦 |
| 2以上低い |
横 |
- |
ここで縦横を両方考慮する必要があるのは「2マス先が同じ高さ、かつ、隣のマスが1低い」場合のみだが、よく考えればこれは縦移動2回により2マス先に移動できるので、横移動を考慮する必要はない。
ということで次のようにすればfの呼び出しは1回で済む
・隣のマスが2以上低く、2マス先が同じ高さなら横移動
・隣のマスとの高低差が1以下なら縦移動
・どちらにも該当しなければ移動できない
abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m);
t=(t=s[p][q]-s[p+n][q+m])>1&s[p][q]==s[p+n+n][q+m+m]?2:abs(t)<2,f(p+n*t,q+m*t);
t=s[p][q],t=t-s[p+n+n][q+m+m]|(t-=s[p+n][q+m])<2?abs(t)<2:2,f(p+n*t,q+m*t);
ということで以上をすべてまとめたものが以下
char s[199][99];
n=1,m;
f(p,q,t,T){
for(T=4*!s[p+99][q]++;T--;t=n,n=m,m=-t)
t=s[p][q],
t=t-s[p+n+n][q+m+m]|(t-=s[p+n][q+m])<2?abs(t)<2:2,
f(p+n*t,q+m*t);
}
main(i,a,b,x,y){
for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[i++]+1););
n=f(a,b)>puts(s[x+99][y]?"YES":"NO");
}
260B
