yukicoder No.424 立体迷路

標準的な迷路を解く問題にちょっとだけ条件が加わったもの。
素直なDFS/BFSで解ける。以下はDFS

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]);
	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)という風に値を更新していくことによってまとめることができる

//before
#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);}
//after
#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

メモ

yukicoderでゆるふわgolf

yukicoder No.424 立体迷路