带你学习Flood Fill算法与最短路模型

一、Flood Fill（连通块问题）

0.简介

Flood Fill（洪水覆盖）

可以在线性的时间复杂内，找到某个点所在的连通块！

注：基于宽搜的思想，深搜也可以做但可能会爆栈

flood fill算法DFS与BFS：

​ DFS：无法求解最短路问题；可能会爆栈（递归层数很深时）；代码简介。当数据范围较小时可以使用

​ BFS：可以求解最短路；不存在爆栈情况；需要自己手写队列

1.池塘计数

农夫约翰有一片 N∗MN∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵*有多少片相连的”W”块。

**

输入格式**

第一行包含两个整数 NN 和 MM。

接下来 NN 行，每行包含 MM 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出格式

输出一个整数，表示池塘数目。

数据范围

1≤N,M≤10001≤N,M≤1000

输入样例：

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出样例：

3

思路：

从前往后遍历，找到一块水（没被标记过的），进行Flood Fill得出所在的连通块，水洼加1。即每一次bfs结束就得到一个连通块（水洼）

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;// 用来存储坐标
queue<PII> q;

const int N = 1010 + 10;
char g[N][N];
bool st[N][N];
int n, m, ans;

//八方向
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

// 找出(x,y)所构成的连通块！
void bfs(int x, int y)
{

    q.push({x, y}), st[x][y] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        //扩展队头（遍历所有邻接点）
        for(int i = 0; i < 8; i ++)
        {
            int tx = t.first + dx[i];
            int ty = t.second + dy[i];

            //细节判断
            if(tx < 0 || tx >= n || ty < 0 || ty >= m ) continue;// 越界
            if(g[tx][ty] == '.' || st[tx][ty]) continue;// 如果是. 或者虽然是水但被标记过了

            //邻接节点入队
            q.push({tx, ty});
            st[tx][ty] = true;

        }
    }
}

int main()
{

    scanf("%d%d", &n, &m);

    //读入地图
    for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            //找到水 且 没有被标记过的 进行foll fill找连通块
            if(g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                ans ++;
            }
        }
    }

    printf("%d", ans);

    return 0;
}

【DFS代码】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, ans;
const int N = 1100;
char g[N][N];

int fx[8]={-1,-1,-1,0,0,1,1,1};
int fy[8]={-1,0,1,-1,1,-1,0,1};

// 如果遇到池塘就计数，并把与他相连通的池塘抽干(用深搜将它们标记为.)

void dfs(int x, int y)
{
    // 将被访问过的水洼标记，避免重复使用
    g[x][y] = '.';

    // 深搜抽干连通的部分
    for(int i = 0; i < 8; i++)
    {
        int tx = x + fx[i];
        int ty = y + fy[i];
        if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && g[tx][ty] == 'W')
        {
            dfs(tx, ty);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j++)
                cin >> g[i][j];

    // 依次遍历每个点，如果是水洼，计数加1，用深搜将连通的水洼抽干
    for(int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j ++ ){
            if(g[i][j] == 'W'){ // 碰到水洼 结果加1，深搜抽干连通的水洼
                dfs(i,j);
                ans ++;
            }
        }
    }

    cout << ans;

    return 0;
}

2.红与黑

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 HH 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；

2）‘#’：红色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

1≤W,H≤20

输入样例：

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0

输出样例：

45

思路：

遍历图，找到起点（但起点），从起点开始flood fill 并统计黑色瓷砖的数量！

【DFS代码实现】

#include <iostream>
#include <cstring>
#include<cstdio>
#include <algorithm>

using namespace std;

const int N = 30;
char g[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m, res;

void dfs(int x, int y)
{
    g[x][y] = '#';//标记，防止重复访问
    res ++;

    for(int i = 0; i < 4; i++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= n || b < 0 || b >= m) continue;
        if(g[a][b] == '#') continue;
        if(g[a][b] == '.')//找到黑色瓷砖，继续深搜
        {
            dfs(a, b);
        }
    }
}

int main()
{
    //多组数据输入
    while(cin >> m >> n, n || m)
    {
        res = 0;//多输入 每次res要置零 不然结果就累加了！
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

        int x, y;
        bool flag = false;
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < m; j ++ )
                if(g[i][j] == '@')
                {
                    x = i;
                    y = j;
                    flag = true;
                }
            if(flag) break;//找到起点（一个起点） 就可以直接跳出循环了
        }
       dfs(x, y);// flood fill
       cout << res << endl;
    }
    return 0;
}

【BFS代码实现】

#include <iostream>
#include <cstring>
#include<cstdio>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
queue<PII> q;

const int N = 30;
char g[N][N];
bool st[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

int bfs(int x, int y)
{
    int res = 1;
    q.push({x, y});
    st[x][y] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(st[a][b]) continue;
            if(g[a][b] != '.') continue;

            q.push({a, b});
            st[a][b] = true;
            res ++;

        }
    }

    return res;

}

int main()
{
    //多组数据输入
    while(cin >> m >> n, n || m)
    {
        memset(st,0,sizeof st);// 多组输入，每次都要恢复！ 为下一次做好准备！
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

        int x, y;
        bool flag = false;
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < m; j ++ )
                if(g[i][j] == '@')
                {
                    x = i;
                    y = j;
                    flag = true;
                }
            if(flag) break;//找到起点（一个起点） 就可以直接跳出循环了
        }
       cout << bfs(x, y) << endl;// flood fill
    }
    return 0;
}

3.城堡问题

 1   2   3   4   5   6   7
#############################
1 #   |   #   |   #   |   |   #
#####---#####---#---#####---#
2 #   #   |   #   #   #   #   #
#---#####---#####---#####---#
3 #   |   |   #   #   #   #   #
#---#########---#####---#---#
4 #   #   |   |   |   |   #   #
#############################
        (图 1)

#  = Wall
|  = No wall
   -  = No wall

   方向：上北下南左西右东。

图1是一个城堡的地形图。

请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。

城堡被分割成 m∗n个方格区域，每个方格区域可以有0~4面墙。

注意：墙体厚度忽略不计。

输入格式

第一行包含两个整数 mm 和 n，分别表示城堡南北方向的长度和东西方向的长度。

接下来 mm 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。

每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。

例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。

城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。

输入的数据保证城堡至少有两个房间。

输出格式

共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。

数据范围

1≤m,n≤50,

0≤P≤15

输入样例：

4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

输出样例：

5
9

思路：

相邻的点没有墙则表示连通，一个房间则相当于是一个连通块。即，找所有的连通块！—— Flood Fill

从前往后遍历，把每一个连通块找出来，找的时候统计两个数，一个是面积另一个是连通块的数量

本题难点在于输入：（并非裸生生的给你坐标）

二进制只相差一位，因此可以使用移位法！

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
queue<PII> q;

const int N = 50 + 10;
int g[N][N];
bool st[N][N];
int m, n;

int bfs(int x, int y)
{
    //西北东南
    int dx[4] = {0, -1, 0, 1};
    int dy[4] = {-1, 0, 1, 0};

    int area = 0;

    q.push({x, y}), st[x][y] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        area ++;//面积加1

        for(int i = 0; i < 4; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];

            if(a < 0 || a >= n || b < 0 || b >= m) continue;//越界
            if(st[a][b]) continue;//标记过了
            if(g[t.first][t.second] >> i & 1) continue;//有墙

            q.push({a, b});
            st[a][b] = true;

        }
    }

    return area;
}

int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

     int area = 0, cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if(!st[i][j])
            {
                area = max(area, bfs(i, j));
                cnt ++;
            }
    cout << cnt << endl;
    cout << area << endl;
    return 0;
}

4.全球变暖

你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 22 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......
.......
.......
.......
....#..
.......
.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数N。

以下 N 行 N 列，包含一个由字符”#”和”.”构成的N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出格式

一个整数表示答案。

数据范围

1≤N≤1000

输入样例1：

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出样例1：

1

输入样例2：

9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........

输出样例2：

1

思路：

遍历所有未遍历过的陆地，通过bfs计算出当前位置连通陆地的数量total，以及被淹没陆地的数量bound,若total == bound表示完整淹没的一个岛屿

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
queue<PII> q;

const int N = 1010;
char g[N][N];
bool st[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n;
//total：当前连通块#的数量 bound：被淹没的#的数量
void bfs(int x, int y, int& total, int& bound)
{
    q.push({x, y});
    st[x][y] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        total ++;//'#'加1

        bool is_bound = false;//判断岛屿是否被淹没
        for(int i = 0; i < 4; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(st[a][b]) continue;
            if(g[a][b] == '.')//与#相邻的点是海. 说明该陆地#可以被淹没
            {
                is_bound = true;
                continue;
            }
            //未被访问过的#
            q.push({a, b});
            st[a][b] = true;
        }

        if(is_bound) bound ++;//可以被淹没，被淹没#的数量 bound ++
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if(!st[i][j] && g[i][j] == '#')
            {
                int total = 0, bound = 0;
                bfs(i, j, total, bound);
                if(total == bound) cnt ++;//如果连通块中所有的陆地# 都与海. 相邻，说明会被完全淹没
            }
    printf("%d", cnt);    

    return 0;
}

5.山峰和山谷

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为FGD想要旅行的区域，地图被分为 n×nn×n 的网格，每个格子 (i,j)(i,j) 的高度 w(i,j)w(i,j) 是给定的。

若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j)(i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)。

我们定义一个格子的集合 SS 为山峰（山谷）当且仅当：

1. SS 的所有格子都有相同的高度。
2. SS 的所有格子都连通。
3. 对于 ss 属于 SS，与 ss 相邻的 s′s′ 不属于 SS，都有 ws>ws′ws>ws′（山峰），或者 ws<ws′ws<ws′（山谷）。
4. 如果周围不存在相邻区域，则同时将其视为山峰和山谷。

你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入格式

第一行包含一个正整数 nn，表示地图的大小。

接下来一个 n×nn×n 的矩阵，表示地图上每个格子的高度 ww。

输出格式

共一行，包含两个整数，表示山峰和山谷的数量。

数据范围

1≤n≤10001≤n≤1000,

0≤w≤1090≤w≤109

输入样例1：

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

输出样例1：

2 1

输入样例2：

5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7

输出样例2：

3 3

样例解释

样例1：

样例2：

根据题目描述

1、没有比它高的叫山峰

2、没有比它矮的叫山谷

3、还存在又比它高，又比它矮的不算山峰也不算山谷

步骤

• 找到高度一致的连通块，若该连通块周围

  • 没有存在比它高的则该连通块叫山峰

  • 没有存在比它矮的则该连通块叫山谷

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
queue<PII> q;

const int N = 1010;
int h[N][N];
bool st[N][N];

//八方向
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n;

void bfs(int x, int y, bool& has_higher, bool& has_lower)//通过引用传回
{
    q.push({x, y});
    st[x][y] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 8; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(h[a][b] != h[t.first][t.second])//山脉边界:判断是否在同一个山脉里面
            {
                if(h[a][b] > h[t.first][t.second]) has_higher = true;//存在比它高的
                else has_lower = true;//存在比它低的
            }
            //高度相等且未遍历 说明要在同一个连通块当中 邻接节点加入队列 后续继续扩展它
            else if(!st[a][b])
            {
                q.push({a, b});
                st[a][b] = true;
            }
        }
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &h[i][j]);

    int peak = 0, valley = 0;
    //从前往后遍历每个格子
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if(!st[i][j])
            {
                bool has_higher = false, has_lower = false;//用来维护每一个连通块
                bfs(i, j, has_higher, has_lower);//得到一个连通块 根据两个布尔值的情况判断！
                if(!has_higher) peak ++;//只要没有比它高的————山峰
                if(!has_lower) valley ++;//只要没有比它矮的————山谷
                //注：不能加else 存在既不是山峰也不是山谷的情况
            }
    printf("%d %d", peak, valley);        

    return 0;
}

6.奶牛选美

听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。

不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。

牛皮可用一个 N×M 的字符矩阵来表示，如下所示：

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中，X 表示斑点部分。

如果两个 X 在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点。

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。

在上面的例子中，他只需要给三个 .. 区域内涂色即可（新涂色区域用 ∗ 表示）：

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

输入格式

第一行包含两个整数 N 和 M。

接下来 N 行，每行包含一个长度为 M 的由 X 和 .. 构成的字符串，用来表示描述牛皮图案的字符矩阵。

输出格式

输出需要涂色区域的最少数量。

数据范围

1≤N,M≤50

输入样例：

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

输出样例：

3

补充：曼哈顿距离

二维坐标下（坐标系）的计算公式：

欧氏距离里的距离计算：

曼哈顿距离中的距离计算：

曼哈顿距离也叫出租车距离（出租车很难以欧氏距离的方式到达另一地点（可能存在障碍物）），用来标明两个点在标准坐标系上的绝对轴距总和。

图中红线代表曼哈顿距离，绿色代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离，即d(i,j)=|xi-xj|+|yi-yj|。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。

【曼哈顿网格的应用场景和意义】

曼哈顿距离示意图在早期的计算机图形学中，屏幕是由像素构成，是整数，点的坐标也一般是整数，原因是浮点运算很昂贵，很慢而且有误差，如果直接使用AB的欧氏距离(欧几里德距离：在二维和三维空间中的欧氏距离的就是两点之间的距离），则必须要进行浮点运算，如果使用AC和CB，则只要计算加减法即可，这就大大提高了运算速度，而且不管累计运算多少次，都不会有误差。

【代码实现】

思路：

• 从到到尾遍历，找到'X'，然后flood fill 找出两个连通块
• 将两个连通块的所有点（坐标）分别存储到两个集合当中
• 枚举两个集合的所有点对，通过曼哈顿距离公式求解最优解

时间复杂度：O(n*n)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
vector<PII>points[2];// 用vector将两个连通块得坐标存储下来

const int N = 60;
char g[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

void dfs(int x, int y, vector<PII>& pos)
{
    g[x][y] = '.';//标记
    pos.push_back({x, y});//各个X的坐标记录到集合中

    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X')
        {
            dfs(a, b, pos);
        }

    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    for (int i = 0, k = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++)
            if(g[i][j] == 'X')
            {
                //dfs flood fill得出连通块，并将连通块的点存储到集合中
                dfs(i, j, points[k ++]);
            }
    //这样就得到了两个连通块的点，接下就枚举两个集合中的所有点 通过曼哈顿距离求最优解
    int res = 1e8;
    for(auto &a : points[0])
        for(auto &b : points[1])
            res = min(res, abs(a.first - b.first) + abs(a.second - b.second) - 1);
            //直接曼哈顿距离求的是两点间能互相走到需要的步数， 这题相当于问过程中需要经过的点数， 所以要减一
    cout << res;        

    return 0;
}

注：

​ 对于任意两个点求最短距离，曼哈顿距离不一定成立，但对于其中距离最近的两个点（最优解） 曼哈顿距离 一定是正确的！

反证法：假设两个点之间的距离是最优解，如果求解出来的距离不是最短路，那么就说明两个初始起终点之间存在障碍物，那么起点或者终点就可以调换到障碍物的位置上，距离就会变短，那么就与条件假设矛盾了！

二、最短路模型

0.简介

当所有的边权都相等时，BFS搜索可以得到起点到某个点的最短路（单源最短路径问题）！

1.走迷宫

我们对st标记数组进行扩展，在起到标记作用的同时，还起到记录各点到起点的最短距离作用！——d[N][N]

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 mm 个整数（0或 1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

8

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
queue<PII> q;

const int N = 110;
int g[N][N];
int d[N][N]; //存放各个点到起点的距离

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

int bfs()
{
    memset(d, -1, sizeof d);//初始距离全部设置为-1 表示该点未被访问过（记录距离的同时，起到了st数组的作用）
    q.push({0, 0});
    d[0][0] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;//越界
            if(g[a][b]) continue;//撞墙
            if(d[a][b] != -1) continue;//该点被访问过

            q.push({a, b});
            d[a][b] = d[t.first][t.second] + 1;//更新距离

        }
    }

    return d[n - 1][m - 1];
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++)
            cin >> g[i][j];

    cout << bfs();        

    return 0;
}

2.迷宫问题

上述第1题走迷宫的扩展版，BFS如何记录路径问题（最短路）！

BFS常常用到标记数组st，同样的我们对st数组进行扩展，在起到标记作用的同时，起到记录路径的作用！

pair<int , int> pre[N][N]——存放当前位置的前驱（看看这个点是从哪里来的），当我们走到终点时，就可以反推到前一步在哪，进而得出最短路的路径！

给定一个 n×n 的二维数组，如下所示：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。

输出格式

输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。

按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。

数据范围

0≤n≤1000

输入样例：

5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
queue<PII> q;

const int N = 1010;
int g[N][N];
PII pre[N][N];// 记录当前位置的前驱

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n;

void bfs(int x, int y)
{
    q.push({x, y});
    pre[0][0] = {0, 0};//起点的前驱（不用标记也行，我们存的是点的前驱！）

    memset(pre, -1, sizeof pre);//pre数组存放这个点的上一个点，初始化为-1

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];

            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(g[a][b]) continue;
            if(pre[a][b].first != -1) continue;//当前点被访问过

            q.push({a, b});
            pre[a][b] = t;
        }

    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &g[i][j]);

    bfs(n - 1, n - 1);//逆序搜索,正序打印

    PII end(0, 0);//定义起点
    while(true)
    {
        printf("%d %d\n", end.first, end.second);// 从前点开始输出路径
        if(end.first == n - 1 && end.second == n - 1) break;// 到了终点
        end = pre[end.first][end.second];// 没到终点拿到前驱位置
    }
    return 0;
}

3.武士风度的牛

这题也是第1题走迷宫的扩展，求某一个起点到某一个终点的最短距离，不同的是这头牛是以马走日的形式遍历！

农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。

这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。

虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个x，y 的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。

现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。

The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。

这里有一个地图的例子：

             11 | . . . . . . . . . .
             10 | . . . . * . . . . .
              9 | . . . . . . . . . .
              8 | . . . * . * . . . .
              7 | . . . . . . . * . .
              6 | . . * . . * . . . H
              5 | * . . . . . . . . .
              4 | . . . * . . . * . .
              3 | . K . . . . . . . .
              2 | . . . * . . . . . *
              1 | . . * . . . . * . .
              0 ----------------------
                                    1
                0 1 2 3 4 5 6 7 8 9 0

The Knight 可以按照下图中的A,B,C,D… 这条路径用 55 次跳到草的地方（有可能其它路线的长度也是 5）：

             11 | . . . . . . . . . .
             10 | . . . . * . . . . .
              9 | . . . . . . . . . .
              8 | . . . * . * . . . .
              7 | . . . . . . . * . .
              6 | . . * . . * . . . F<
              5 | * . B . . . . . . .
              4 | . . . * C . . * E .
              3 | .>A . . . . D . . .
              2 | . . . * . . . . . *
              1 | . . * . . . . * . .
              0 ----------------------
                                    1
                0 1 2 3 4 5 6 7 8 9 0

注意： 数据保证一定有解。

输入格式

第 1 行： 两个数，表示农场的列数 C 和行数 R。

第 2..R+1 行: 每行一个由 C 个字符组成的字符串，共同描绘出牧场地图。

输出格式

一个整数，表示跳跃的最小次数。

数据范围

1≤R,C≤150

输入样例：

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

输出样例：

5

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
queue<PII> q;

const int N = 160;
char g[N][N];
int d[N][N];

//日字形八方向
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int n, m;

int bfs()
{
    int x, y;// 起点位置
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if(g[i][j] == 'K')
                x = i, y = j;

    q.push({x, y});
    memset(d, -1, sizeof d);
    d[x][y] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 8; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == '*') continue;
            if(d[a][b] != -1) continue;
            if(g[a][b] == 'H') return d[t.first][t.second] + 1;

            q.push({a, b});
            d[a][b] = d[t.first][t.second] + 1;
        }
    }

    return -1;//没有答案

}

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    cout << bfs();

    return 0;
}

4.抓住那头牛

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。

农夫有两种移动方式：

1. 从 X 移动到 X−1 或 X+1，每次移动花费一分钟
2. 从 X 移动到 2∗X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

输入格式

共一行，包含两个整数N和K。

输出格式

输出一个整数，表示抓到牛所花费的最少时间。

数据范围

0≤N,K≤105

输入样例：

5 17

输出样例：

4

思路：

题目讲述一共有3种移动情况且权重一致（都为1）

• 从X移动到 X−1
• 从X移动到 X+1
• 从 X 移动到 2∗X

相当于X 与X - 1,X + 1,2 * X ,各连一条边,从n开始进行bfs到k，dist[k]表示k点到n点的最短距离

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

queue<int> q;
int d[N];

int n, k;

int bfs()
{

    memset(d, -1, sizeof d);
    q.push(n);
    d[n] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        if(t == k) return d[k];

        if(t + 1 < N && d[t + 1] == -1)//在范围内 且未被访问
        {
            d[t + 1] = d[t] + 1;
            q.push(t + 1);
        }
        if(t - 1 >= 0 && d[t - 1] == -1)
        {
            d[t - 1] = d[t] + 1;
            q.push(t - 1);
        }
        if(t * 2 < N && d[t * 2] == -1)
        {
            d[t * 2] = d[t] + 1;
            q.push(t * 2);
        }
    }

    return - 1;
}

int main()
{
    cin >> n >> k;

    cout << bfs();

    return 0;
}

三、总结

学习内容参考：

百度百科

acwing算法基础课、提高课

注：如果文章有任何错误或不足，请各位大佬尽情指出，评论留言留下您宝贵的建议！如果这篇文章对你有些许帮助，希望可爱亲切的您点个赞推荐一手，非常感谢啦