首页 > 代码库 > 林月如和女飞贼 dessnitch
林月如和女飞贼 dessnitch
【题目描述】：
已知林月如和女飞贼站在一个矩阵中，矩阵中有某些障碍物不可穿越。月如使出的铜钱镖可攻击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 node20 {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 }
林月如和女飞贼 dessnitch
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。