【题目描述】：
已知林月如和女飞贼站在一个矩阵中，矩阵中有某些障碍物不可穿越。月如使出的铜钱镖可攻击8个方向，但不可穿越障碍物（可视为不能穿墙的重狙）。每个单位时间，月如可向上下左右4个方向移动一格，攻击不浪费时间。当然，月如想尽快结束这场无聊的战斗，所以她想在最短的时间内消灭女飞贼。
【输入描述】：
第一行为2个数N,M表示矩阵的规模(N为高,M为宽，不操过128)。
接下来是N*M的矩阵,O表示空地,X表示障碍物。
下面是若干行数据（不操过10），每行为一对数据，分别是女飞贼的位置和林月如的位置，显然她们都不可能在障碍物上。
以"0 0 0 0"为输入结束标志。
【输出描述】：
每一组数据输出一行，仅一个整数，表示能消灭掉女飞贼的最短时间。
显然若能直接打到女飞贼，则时间为0。
若无法消灭，则输出"Impossible!"。（不含引号）
|
【样例输入】 |
【样例输出】 |
|
3 4 OXXO XXOO XOOO 3 2 2 4 3 3 1 1 0 0 0 0 |
1 Impossible! |
【数据范围及描述】：
BFS搜索水题，老师布置的轻松过！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 8 const int maxn=130; 9 const int dx[]={1,-1,0,0}; 10 const int dy[]={0,0,1,-1}; 11 const int bx[]={1,1,1,-1,-1,-1,0,0}; 12 const int by[]={1,-1,0,1,-1,0,1,-1}; 13 int N,M; 14 char g[maxn][maxn]; 15 bool vis[maxn][maxn]; 16 int xa,ya,xb,yb; 17 int ans; 18 19 struct node 20 { 21 int x,y,num; 22 }; 23 24 bool bfs() 25 { 26 queue<node> Q; 27 memset(vis,false,sizeof(vis)); 28 vis[xa][ya]=true; 29 Q.push((node){xa,ya,0}); 30 node top; 31 while(!Q.empty()) 32 { 33 top=Q.front(); 34 Q.pop(); 35 int xx,yy; 36 for(int i=0;i<8;i++) 37 { 38 xx=top.x; 39 yy=top.y; 40 while(1) 41 { 42 xx+=bx[i]; 43 yy+=by[i]; 44 if(xx<1||xx>N||yy<1||yy>M) break; 45 if(g[xx][yy]==‘X‘) break; 46 if(xx==xb&&yy==yb) 47 { 48 ans=top.num; 49 return true; 50 } 51 } 52 } 53 for(int i=0;i<4;i++) 54 { 55 xx=top.x+dx[i]; 56 yy=top.y+dy[i]; 57 if(xx>=1&&xx<=N&&yy>=1&&yy<=M&&!vis[xx][yy]&&g[xx][yy]!=‘X‘) 58 { 59 vis[xx][yy]=true; 60 Q.push((node){xx,yy,top.num+1}); 61 } 62 } 63 } 64 return false; 65 } 66 67 68 int main() 69 { 70 scanf("%d %d\n",&N,&M); 71 for(int i=1;i<=N;i++) 72 scanf("%s\n",g[i]+1); 73 while(cin>>xb>>yb>>xa>>ya) 74 { 75 if(xa==0&&ya==0&&xb==0&&yb==0) break; 76 if(bfs()) printf("%d\n",ans); 77 else printf("Impossible!\n"); 78 } 79 return 0; 80 }
原文：http://www.cnblogs.com/cnblogsLSY/p/5824174.html
