#include<cstdio>#include<iostream>#include<queue>#include<cstring>using namespace std;struct node{ int x,y;}s;int dx[]={-1,1,0,0};int dy[]={0,0,-1,1};char map[80][80];int step[80][80];int n,m,x1,y1,x2,y2;bool ok(int x,int y){ if(x>=0 && x<=n+1 && y>=0 && y<=m+1) return true; return false;}int bfs(int x1,int y1,int x2,int y2){ queue<node> q; s.x = x1; s.y = y1; step[s.x][s.y] = 0; map[x1][y1] = ' '; map[x2][y2] = ' '; q.push(s); node cur,next,u; while(!q.empty()) { u = q.front(); q.pop(); if(u.x == x2 && u.y == y2) return step[x2][y2]; for(int i=0;i<4;i++) { cur = u; next.x = cur.x+dx[i]; next.y = cur.y+dy[i]; while(ok(next.x,next.y) && map[next.x][next.y]==' ' && step[next.x][next.y]==-1) { step[next.x][next.y] = step[u.x][u.y]+1; q.push(next); cur = next; next.x = cur.x+dx[i]; next.y = cur.y+dy[i]; } } } return -1;}int main(){ int cas=1; while(scanf("%d%d",&m,&n)!=EOF) //n行m列 { if(m==0 && n==0) break; getchar(); for(int i=1;i<=n;i++) gets(map[i]+1); for(int i=0;i<=m+1;i++) { map[0][i]=' '; map[n+1][i]=' '; } for(int j=0;j<=n+1;j++) { map[j][0]=' '; map[j][m+1]=' '; } int tes=1; printf("Board #%d:n",cas++); while(1) { scanf("%d%d%d%d",&y1,&x1,&y2,&x2); if(x1==0 && y1==0 && x2==0 && y2==0) { //cas++; break; } memset(step,-1,sizeof(step)); printf("Pair %d: ",tes); int ans = bfs(x1,y1,x2,y2); if(ans == -1) printf("impossible.n"); else printf("%d segments.n",ans); tes++; map[x1][y1] = map[x2][y2] ='X'; } printf("n"); } return 0;}
