1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7  8 const int N=80; 9 int r,c,sx,sy,ex,ey,ans;10 int vis[N][N],Map[N][N];11 int dx[4]={1,-1,0,0};12 int dy[4]={0,0,1,-1};13 bool isin(int x,int y)14 {15     return x>=0&&x<=r+1&&y>=0&&y<=c+1;16 }17 struct node18 {19     int x,y,s;20 };21 node a,b;22 queue<node> q;23 void BFS()24 {25     int i,j,k,x,y;26     while(!q.empty())27     {28         a=q.front(); q.pop();29         for(k=0;k<4;k++)30         {31             x=a.x,y=a.y;32             while(1)33             {34                 x+=dx[k]; y+=dy[k];35                 if(!isin(x,y)) break;36                 if(x==ex&&y==ey){ans=a.s;return ;}37                 if(!vis[x][y])38                 {39                     b.x=x; b.y=y;b.s=a.s+1;40                     q.push(b);41                     vis[x][y]=1;42                 }43                 else break;44             }45         }46     }47 }48 int main()49 {50     //freopen("test.txt","r",stdin);51     int cas=0,t;52     while(scanf("%d%d",&c,&r)!=EOF&&c)53     {54         int i,j;55         char ch[100];56         memset(Map,0,sizeof(Map));57         gets(ch);58         for(i=1;i<=r;i++)59         {60             gets(ch);61             for(j=0;j<c;j++)62                 if(ch[j]==‘X‘) Map[i][j+1]=1;63         }64         printf("Board #%d:\n",++cas);65         t=0;66         while(scanf("%d%d%d%d",&sy,&sx,&ey,&ex)!=EOF&&sy)67         {68             for(i=0;i<=r+1;i++)69                 for(j=0;j<=c+1;j++)70                     vis[i][j]=Map[i][j];71             while(!q.empty()) q.pop();72             a.x=sx,a.y=sy,a.s=1;73             q.push(a);74             ans=-1;75             BFS();76             printf("Pair %d: ",++t);77             if(ans==-1) printf("impossible.\n");78             else printf("%d segments.\n",ans);79         }80         printf("\n");81     }82     return 0;83 }