本专栏上一篇：【BFS】魔板（c++基础算法）_静渊隐者的博客-CSDN博客
目录
一.读题
①题面
【宽搜（难度：4）】海上救援任务
【题意】
广阔的大海地图可以由矩形阵列表示。
矩阵的元素由数字0和1组成。0表示海水。数字1代表军舰。
同一舰队的定义为沿军舰数字上下左右还是军舰数字1则为同一舰队。
求给定矩形阵列的舰队个数。如:矩阵
0111100011
1011110100
1011100111
0000000011
有4个舰队。
其中有艘军舰发生故障，负责救援的人员从固定的救援军舰赶往故障处。处于安全考虑，救援人员只能通过舰队内部到达故障点。
【输入格式】
第一行两个整数n，m （1 < = n，m< ＝ 100）
下来是n×m矩阵
下来一行K（1 < = K < =2000) ，代表下来K行有K个询问。每行为X1,Y1,X2,Y2代表两艘军舰的海上坐标。
【输出格式】
如果两艘军舰属于同一舰队那么输出它们之间最短的内部距离，若两艘军舰不属于同一舰队，那么请输出"Impossible".
注意： 舰队由军舰构成。^_^
【样例输入】
4 10
0111100011
1011110100
1011100111
0000000011
2
1 3 2 6
1 3 4 10
【样例输出】
4
Impossible
②题意
若存在xs,ys在不经过零的情况下到达xe,ye的路线，则输出最短路径；否则，输出Impossible
三.做题
可以说，这道题是百年不遇的水题，因此就不解释了。
唯一值得注意的是，存入地图的操作。
因为输入的地图不含空格，因此必须以字符形式输入。输入后，可依托ASCII码进行运算，将其转换为int类型的数组。
for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { char ch; cin>>ch; a[i][j]=ch-'0'; } }
四.AC代码
不写注释啦！
#include<bits/stdc++.h> using namespace std; struct node{ int x,y,ans; }; queue<node>q; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int a[105][105]; int n,m,t,bo[105][105]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { char ch; cin>>ch; a[i][j]=ch-'0'; } } scanf("%d",&t); while(t--) { memset(bo,0,sizeof(bo)); node xs,xe; bool flag=false; xs.ans=0; scanf("%d%d%d%d",&xs.x,&xs.y,&xe.x,&xe.y); q.push(xs); while(!q.empty()) { for(int i=0;i<4;i++) { node ne; ne.x=q.front().x+dx[i],ne.y=q.front().y+dy[i]; if(bo[ne.x][ne.y]==0&&ne.x>=0&&ne.y>=0&&ne.x<=n&&ne.y<=m&&a[ne.x][ne.y]==1) { ne.ans=q.front().ans+1; bo[ne.x][ne.y]=1; q.push(ne); if(ne.x==xe.x&&ne.y==xe.y) { flag=true; printf("%d\n",q.back().ans); break; } } } if(flag) break; q.pop(); } if(!flag) printf("Impossible\n"); } }
最后
没什么要说的，不过说一句话：普及组训练营暂时停更 暂时停更。
