——以“营救”为例
题目描述
铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。
通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成(/ n×n /)个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。
为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。
输入格式
第一行为n,下面是一个 (/ n×n /) 的0、1矩阵，表示海洋地图 最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。 (/ 1<=n<=1000 /)
题目分析
广搜模板题，本题要求一个路线的最短距离，显然是通过遍历从起点开始的所有情况。
广搜的实现与深搜不同，深搜的情况转移是通过在函数的递归而将其分别存储在每一个树节点中，可以戳这边了解。而广搜则是将每一个分支节点存储在一个队列中，先进先出，而存储形式则就是依赖于结构体，这一题我们需要存储的显然就是当前位置（步长可以不存储）。每对一个节点进行处理就是将周围能走的所有节点再次压入队列中的过程
我理解广搜的重点和难点就是判重，广搜与深搜同样都是全NP算法，一旦不加以优化便回很容易超出时空限制
在这里我们将所有走过的节点标记为已经走过便实现了一个判重的效果，具体的小技巧可看代码注释
Accepted Code
/*
* @Author: Gehrychiang
* @Date: 2020-01-30 12:35:39
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <bits/stdc++.h>
using namespace std;
int n, stx, sty, enx, eny, cnt = 0;
char sea[1005][1005];
struct $
{
int x;
int y;
int step;
};
queue<$> q;
void bfs(int x, int y)
{
$ in;
in.x = x;
in.y = y;
in.step = 0;
q.push(in);
//开始广搜
while (!q.empty())
{
$ tmp, nex;//当前节点与下一节点
tmp = q.front();
q.pop();
if (tmp.x == enx && tmp.y == eny)
{
cnt = tmp.step;
return;
}
nex.step = tmp.step + 1;
if (sea[tmp.x - 1][tmp.y] == '0')//只要可以走且没有走过
{
sea[tmp.x - 1][tmp.y] = '1';//走这一步，将这一步标记为“陆地”起到不在走的效果(并且是直接将即将走的这个节点标记，可以有效降重)
nex.x = tmp.x - 1;
nex.y = tmp.y;
q.push(nex);
}
if (sea[tmp.x + 1][tmp.y] == '0')
{
sea[tmp.x + 1][tmp.y] = '1';
nex.x = tmp.x + 1;
nex.y = tmp.y;
q.push(nex);
}
if (sea[tmp.x][tmp.y - 1] == '0')
{
sea[tmp.x][tmp.y - 1] = '1';
nex.x = tmp.x;
nex.y = tmp.y - 1;
q.push(nex);
}
if (sea[tmp.x][tmp.y + 1] == '0')
{
sea[tmp.x][tmp.y + 1] = '1';
nex.x = tmp.x;
nex.y = tmp.y + 1;
q.push(nex);
}
}
return;
}
int main()
{
cin >> n;
for (int x = 0; x <= n + 1; x++)//在外圈也标记上一圈“陆地”可以防止溢出
{
for (int y = 0; y <= n + 1; y++)
{
sea[x][y] = '1';//将所有位置标记为 “陆地”
}
}
for (int x = 1; x <= n; x++)
{
for (int y = 1; y <= n; y++)
{
cin >> sea[x][y];
}
}
cin >> stx >> sty >> enx >> eny;
sea[stx][sty]='1';
bfs(stx, sty);
cout << cnt << endl;
return 0;
}