#include #include #include using namespace std; int w,h; int kx,ky,mx,my; char g[100][100]; int dirs[]={0,-1,1,0,0,1,-1,0}; int get_dir(int x, int y) { for (int i=0;i<4;++i) { int nx=x+dirs[2*i],ny=y+dirs[2*i+1]; if (nx<0||nx>=w||ny<0||ny>=h) continue; if (g[nx][ny]=='.') return i; } assert(0); } int enc(int x, int y, int dir) { return (x*h+y)*4+dir; } int enc2(int x1, int y1, int dir1, int x2, int y2, int dir2) { return enc(x1,y1,dir1)*32768+enc(x2,y2,dir2); } void dec(int v, int& x, int& y, int& dir) { dir=v%4; v/=4; y=v%h; v/=h; x=v%w; } void dec2(int v, int& x1, int& y1, int& dir1, int& x2, int& y2, int& dir2) { dec(v%32768,x2,y2,dir2); dec(v/32768,x1,y1,dir1); } void move(int x, int y, int dir, int& nx, int& ny) { nx=x,ny=y; while(1) { int nnx=nx+dirs[2*dir],nny=ny+dirs[2*dir+1]; if (nnx<0||nnx>=w||nny<0||nny>=h) return; if (g[nnx][nny]=='#') return; nx=nnx,ny=nny; } } int solve1() { int kkx,kky,kdir=get_dir(kx,ky); move(kx,ky,kdir,kkx,kky); queue q; set seen; { int v=enc(kkx,kky,kdir); q.push(v); seen.insert(v); } while(!q.empty()) { int v=q.front(); q.pop(); int x1,y1,dir1; dec(v,x1,y1,dir1); if (x1==mx&&y1==my) return 1; for (int i=-1;i<=1;i+=2) { int ndir1=(dir1+i+4)%4; int nx1,ny1; move(x1,y1,ndir1,nx1,ny1); int nv=enc(nx1,ny1,ndir1); if (!seen.count(nv)) { q.push(nv); seen.insert(nv); } } } return 0; } int solve2() { int kkx,kky,kdir=get_dir(kx,ky); move(kx,ky,kdir,kkx,kky); int mmx,mmy,mdir=get_dir(mx,my); move(mx,my,mdir,mmx,mmy); queue q; set seen; for (int i=0;i<4;++i) { int v=enc2(kkx,kky,kdir,kx,ky,i); q.push(v); seen.insert(v); } while(!q.empty()) { int v=q.front(); q.pop(); int x1,x2,dir1,y1,y2,dir2; dec2(v,x1,y1,dir1,x2,y2,dir2); if (x1==mx&&y1==my&&x2==mmx&&y2==mmy&&dir2==mdir) return 1; for (int i=-1;i<=1;i+=2) { int ndir1=(dir1+i+4)%4; int nx1,ny1; move(x1,y1,ndir1,nx1,ny1); int nx2=x2,ny2=y2; int ndir2=(dir2+i+4)%4; while(1) { int wx=nx2+dirs[2*ndir2],wy=ny2+dirs[2*ndir2+1]; if (0<=wx&&wx=w||nny<0||nny>=h) break; if (g[nnx][nny]=='#') break; nx2=nnx,ny2=nny; } } } return 0; } int main() { while(scanf("%d%d",&w,&h),w|h) { for (int i=0;i