2.1.1 BFS中的Flood Fill和最短路模型

BFS特点

  1. 求最小->第一次搜到恰为最小距离

  2. 基于迭代，不会爆栈（一般1M，十万层）

类型最小距离->从内部一点到另一点的最小距离
eg.走迷宫

最小步数->整体视为一个状态，状态的变换的最小步数(状态本身作为一个点，每次变换视为一步，问题是状态之间的逻辑关系)
eg.八数码

一. Flood Fill算法

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

使用BFS的过程模拟洪水覆盖的过程–从四周开始扩散–填充整个连通块

连通类型四连通八连通

1. AcWing 1097. 池塘计数

注意双层逻辑：先遍历每个格子，每个格子再进行BFS搜索过程。需进行标记–判重。

BFS使用队列实现，队列中存储下标，二维时可以使用pair

注意是否开始搜索的判断条件要想清楚

搜索时注意遍历方法和边界条件

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// BFS中的Flood Fill——AcWing 1097. 池塘计数
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII; 

const int N = 1010, M = N * N;

int n, m;
char g[N][N]; // 存图，注意使用char
PII q[M]; // 数组模拟队列时，数组大小为所有元素大小
bool st[N][N]; // 标记是否搜索过，避免重复

// 传入坐标位置参数
void bfs(int sx, int sy){
    // 数组模拟队列。bfs基于迭代，每次调用使用一个队列
    int hh = 0, tt = 0;// 初始化
    // 分别标记队列要取出结点的位置，存取结点的前一个位置
    
    q[0] = {sx, sy};
    // 初始状态入队列
    st[sx][sy] = true;
    // 进行标记

    while (hh <= tt){ // 队列不为空
        PII t = q[hh ++]; // 取出队头元素

        // 拓展队列元素
        // 枚举所有可能的移动方向
        // 注意区分四连通和八连通
        // 这里要注意八的遍历方式
        // 暴力枚举3 X 3 矩阵并挖掉中间格子
        for (int i = t.x - 1; i <= t.x + 1;++ i)
            for (int j = t.y - 1; j <= t.y + 1; ++ j){
                if (i == t.x && j == t.y) continue;
                // 挖掉中间格子
                if (i < 0 || i >= n || j < 0 || j >= m)  
                    continue;
                // 注意判断是否越界
                if (g[i][j] == '.' || st[i][j])      
                // 是否满足条件 
                    continue;
                q[++ tt] = {i, j};
                // 满足条件的入列
                st[i][j] = true; 
                // 标记已搜索过
            }

    }
}

int main(){
    scanf("%d%d", &n, &m);
    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 < m; ++ j)
            if (g[i][j] == 'W' && !st[i][j]) 
            // 是否满足条件
            // 这里的代码的书写的思路是要掌握的，一定不要乱，不要寻求直接找到符合条件的再遍历，而是全部遍历再判断是否符合条件
            {
                bfs(i, j);
                // 符合条件的进行广度优先搜索
                cnt ++;
            }
    printf("%d\n", cnt);
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# BFS中的Flood Fill——AcWing 1097. 池塘计数
# 使用库函数deque，速度更快
from collections import deque
# 双向队列deque是栈和队列的一种广义实现，是类似于list的容器，可以快速的在队列头部和尾部添加、删除元素

# 注意这里没有另开查重数组，通过直接改变原数组实现标记
def main():
    n, m = map(int, input().split())
    g = [list(input()) for _ in range(n)]
    d_x = (-1, -1, -1, 0, 0, 1, 1, 1)
    d_y = (-1, 0, 1, -1, 1, -1, 0, 1)
    # 不能使用st = [[False]*m]*n这种写法
    # [[0]*n]*m这种方式是直接将[0]*n复制了m遍，是=号复制（注意不是浅拷贝，=与浅拷贝的list id是不同的），
    # 若[0]*n发生了更改，则m个都发生更改。[0]*n作为一个list被共享。
    cnt = 0
    
    def bfs(sx, sy):
        q = deque([(sx, sy)])
        g[sx][sy] = '.'
    
        while q:
            x, y = q.popleft()
            for dx, dy in zip(d_x, d_y):
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and g[nx][ny] == 'W':
                    q.append((nx, ny))
                    g[nx][ny] = '.'
    
    for i, line in enumerate(g):
        for j, ch in enumerate(line):
            if ch == 'W':
                bfs(i, j)
                cnt += 1
    print(cnt)
    
    
if __name__ == "__main__":
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# // BFS中的Flood Fill——AcWing 1097. 池塘计数
# 数组模拟队列    
def main():
    n, m = map(int, input().split())
    g = [list(input()) for _ in range(n)]
    d_x = (-1, -1, -1, 0, 0, 1, 1, 1)
    d_y = (-1, 0, 1, -1, 1, -1, 0, 1)
    q = [0] * (n * m)
    st = [[False] * m for _ in range(n)]
    # 不能使用st = [[False]*m]*n这种写法
    # [[0]*n]*m这种方式是直接将[0]*n复制了m遍，是=号复制（注意不是浅拷贝，=与浅拷贝的list id是不同的），
    # 若[0]*n发生了更改，则m个都发生更改。[0]*n作为一个list被共享。
    cnt = 0
    
    def bfs(sx, sy):
        hh, tt = 0, 0
        q[0] = (sx, sy)
        st[sx][sy] = True
        
        while hh <= tt:
            x, y = q[hh]
            hh += 1
            for dx, dy in zip(d_x, d_y):
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and g[nx][ny] == 'W' and not st[nx][ny]:
                    tt += 1
                    q[tt] = (nx, ny)
                    st[nx][ny] = True
    
    
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'W' and not st[i][j]:
                bfs(i, j)
                cnt += 1
    print(cnt)
    
    
if __name__ == "__main__":
    main()

2. AcWing 1098. 城堡问题

四连通遍历

取二进制中第k位
x >> k & 1
本题注意二进制解码的方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// BFS中的Flood Fill——AcWing 1098. 城堡问题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55, M = N * N;

int n, m;
int g[N][N];
PII q[M];
bool st[N][N];

int bfs(int sx, int sy){
    int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
    // 四连通时的写法
    // 常用技巧：使用偏移量表示移动方向
    // 注意这里的方向顺序必须和西北东南的顺序相对应
    // 只是为了方便后面进行二进制解码

    int hh = 0, tt = 0; 
    // 分别标记队列要取出结点的位置，存取结点的前一个位置
    int area = 0;
    // 初始化

    q[0] = {sx, sy};
    // 初始状态入队
    st[sx][sy] = true;

    while (hh <= tt){ // 队列不为空
        PII t = q[hh ++];
        area ++; 
        // 可以在出队时统计，可以在入队时统计
        // 这里为了避免第一个忘统计，在出队时统计

        // 拓展队列元素
        // 枚举所有可能的移动方向
        for (int i = 0; i < 4; ++ i){
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            // 越界判断
            if (st[a][b]) continue;
            if (g[t.x][t.y] >> i & 1) continue;
            // 使用位运算，解码二进制
            // x >> i & 1 取出x二进制的第i位
            // 根据第i位是否为1判断是否有墙
            // 这里的顺序能成立是因为按照了西北东南的顺序，
            //且题目规定用1表示西墙，2表示北墙，4表示东墙，8表示南墙
            q[++ tt] = {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 cnt = 0, area = 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;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# BFS中的Flood Fill——AcWing 1098. 城堡问题
# 使用库函数deque
from collections import deque

def main():
    n, m = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(n)]
    d_x = [0, -1, 0, 1]
    d_y = [-1, 0, 1, 0]
    st = [[False] * m for _ in range(n)]
    
    def bfs(sx, sy):
        q = deque([[sx, sy]])
        st[sx][sy] = True
        # 不能使用st = [[False]*m]*n这种写法
        # [[0]*n]*m这种方式是直接将[0]*n复制了m遍，是=号复制（注意不是浅拷贝，=与浅拷贝的list id是不同的），
        # 若[0]*n发生了更改，则m个都发生更改。[0]*n作为一个list被共享。
        area = 0
        
        while q:
            x, y = q.popleft()
            area += 1
            for i in range(4):
                nx, ny = x + d_x[i], y + d_y[i]
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if st[nx][ny]:
                    continue
                if g[x][y] >> i & 1:
                    continue
                q.append([nx, ny])
                st[nx][ny] = True
        return area
    
    cnt, area = 0, 0
    for i in range(n):
        for j in range(m):
            if not st[i][j]:
                area = max(area, bfs(i, j))
                cnt += 1
    print(cnt)
    print(area)
    
if __name__ == '__main__':
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# BFS中的Flood Fill——AcWing 1098. 城堡问题
# 数组模拟队列
def main():
    n, m = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(n)]
    d_x = [0, -1, 0, 1]
    d_y = [-1, 0, 1, 0]
    st = [[False] * m for _ in range(n)]
    q = [0] *(m*n)
    
    def bfs(sx, sy):
        q[0] = [sx, sy]
        st[sx][sy] = True
        # 不能使用st = [[False]*m]*n这种写法
        # [[0]*n]*m这种方式是直接将[0]*n复制了m遍，是=号复制（注意不是浅拷贝，=与浅拷贝的list id是不同的），
        # 若[0]*n发生了更改，则m个都发生更改。[0]*n作为一个list被共享。
        area = 0
        hh, tt = 0, 0
        
        while hh <= tt:
            x, y = q[hh]
            hh += 1
            area += 1
            for i in range(4):
                nx, ny = x + d_x[i], y + d_y[i]
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if st[nx][ny]:
                    continue
                if g[x][y] >> i & 1:
                    continue
                tt += 1
                q[tt] = [nx, ny]
                st[nx][ny] = True
        return area
    
    cnt, area = 0, 0
    for i in range(n):
        for j in range(m):
            if not st[i][j]:
                area = max(area, bfs(i, j))
                cnt += 1
    print(cnt)
    print(area)
    
if __name__ == '__main__':
    main()

3. AcWing 1106. 山峰和山谷

本题要判断每个方格和周围方格的关系

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// BFS中的Flood Fill——AcWing 1106. 山峰和山谷
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int h[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy, bool & has_higher, bool & has_lower){
    int hh = 0 ,tt = 0;
    // 分别标记队列要取出结点的位置，存取结点的前一个位置
    // 初始化
    q[0] = {sx, sy};
    // 初始状态入队
    st[sx][sy] = true;

    while (hh <= tt){ // 队列不为空
        PII t = q[hh ++];

        for (int i = t.x - 1; i <= t.x + 1; ++ i)
            for (int j = t.y - 1; j <= t.y + 1; ++ j){
                if (i < 0 || i >= n || j < 0 || j >= n) continue;
                // 判断是否越界
                if (h[i][j] != h[t.x][t.y]){
                    // 判断与周围方格的高度关系
                        if (h[i][j] > h[t.x][t.y]) has_higher = true;
                        else has_lower = true;
                        // 不能提前结束遍历
                        // 要把整个连通块都遍历一遍，防止重复
                }
                else if (!st[i][j]){
                        q[++ tt] = {i, j};
                        // 入队列
                        st[i][j] = true;
                }   
                // 注意这里不能先写if(st[i][j]) continue;
                // 只有未遍历过的才能入队列，但在判断四周是否有高低点时与四周点是否遍历过无关
            }

    }
}

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\n", peak, valley);

    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# BFS中的Flood Fill——AcWing 1106. 山峰和山谷
# 使用库函数deque
from collections import deque

def main():
    n = int(input())
    h = [list(map(int, input().split())) for _ in range(n)]
    st = [[False] * n for _ in range(n)]
     
    def bfs(sx, sy):
        q = deque([[sx, sy]])
        st[sx][sy] = True
        
        has_higher, has_lower = False, False
        # 已经在遍历时判断有不相等
        # 注意这里的逆思维
        # 大于周围所有->山峰，小于周围所有->山谷
        # 不存在大于周围->是山谷, 不存在小于周围->是山峰
        while q:
            x, y = q.popleft()
            for i in range(x - 1, x + 2):
                for j in range(y - 1, y + 2):
                    if i == x and j == y: 
                        continue
                    if i < 0 or i >= n or j < 0 or j >= n:
                        continue
                    # 注意这里的逻辑顺序
                    if h[i][j] > h[x][y]:
                        has_higher = True
                    elif h[i][j] < h[x][y]:
                        has_lower = True
                    elif not st[i][j]:
                        # 只有相等的才会入队列
                        q.append([i, j])
                        st[i][j] = True
        return has_higher, has_lower
                  
    peak, valley = 0, 0   
    for i in range(n):
        for j in range(n):
            if not st[i][j]:
                has_higher, has_lower = bfs(i, j)
                if not has_higher: peak += 1
                if not has_lower: valley += 1
    print(peak, valley)  

if __name__ == '__main__':
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# BFS中的Flood Fill——AcWing 1106. 山峰和山谷
# 数组模拟队列
def main():
    n = int(input())
    h = [list(map(int, input().split())) for _ in range(n)]
    st = [[False] * n for _ in range(n)]
    q = [0] * (n*n);
    
    def bfs(sx, sy):
        q[0] = (sx, sy)
        st[sx][sy] = True;
        hh, tt = 0, 0
        has_higher , has_lower = False, False
        
        while hh <= tt:
            x, y = q[hh]
            hh += 1
            
            for i in range(x - 1, x + 2):
                for j in range(y - 1, y + 2):
                    if i == x and j == y:
                        continue
                    if i < 0 or i >= n or j < 0 or j >= n:
                        continue
                    if h[i][j] > h[x][y]:
                        has_higher = True
                    elif h[i][j] < h[x][y]:
                        has_lower = True
                    elif not st[i][j]:
                        tt += 1
                        q[tt] = (i, j)
                        st[i][j] = True
        return has_higher, has_lower
    
    peak, vallery = 0, 0
    for i in range(n):
        for j in range(n):
            if not st[i][j]:
                has_higher, has_lower = bfs(i, j)
                if not has_higher: peak += 1
                if not has_lower: vallery += 1
    print(peak, vallery)
    
if __name__ == '__main__':
    main()

二. 最短路模型

宽搜具有最短路性质：

当所有边的权重相等时，使用宽搜可以在线性复杂度内得到起点到所有点的最短路（单源最短路）。

第一次搜到一定是最短的，不需要记录额外的距离信息。

特殊的dijkstra算法->权重相同时，按层搜索使队列为优先队列

1. AcWing 1076. 迷宫问题

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// BFS中的最短路模型——AcWing 1076. 迷宫问题
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = N * N;

int n;
int g[N][N];
PII q[M];
PII pre[N][N];
// pre记录最短路中当前位置的前一个位置（从哪个点过来的），也起到了st数组的作用

void bfs(int sx, int sy){
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    
    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0, 0};
    while (hh <= tt){
        PII t = q[hh ++];
        
        for (int i = 0; i < 4 ; ++ i){
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue;
            if (g[a][b] == 1) continue;
            if (pre[a][b].x != -1) continue;
            
            q[++ tt] = {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.x, end.y);
        // 不能直接判断end == {n-1, n-1}
        if (end.x == n - 1&& end.y == n - 1) break;
        end = pre[end.x][end.y];
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# BFS中的最短路模型——AcWing 1076. 迷宫问题 
# 使用库函数deque
from collections import deque

def main():
    n = int(input())
    g = [list(map(int, input().split())) for _ in range(n)]
    pre = [[[-1, -1] for _ in range(n)] for _ in range(n)]
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
  
    def bfs(sx, sy):
        q = deque([[sx, sy]]);
        pre[sx][sy] = [sx, sy]
        
        while q:
            x, y = q.popleft()
            
            for i in range(0, 4):
                a = x + dx[i]
                b = y + dy[i]
                if a < 0 or a >= n or b < 0 or b >= n:
                    continue
                if g[a][b] == 1:
                    continue
                # if pre[a][b] != [-1, -1]:
                #     continue
                g[a][b] = 1
                q.append([a, b])
                pre[a][b] = [x, y]
                    
    bfs(n - 1, n - 1)
    
    i, j = 0, 0 
    while True:
        print(i, j)
        if i == n - 1 and j == n - 1:
            break
        i, j = pre[i][j]
                    
if __name__ == '__main__':
    main()

2.AcWing 188. 武士风度的牛

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// BFS中的最短路模型——AcWing 188. 武士风度的牛
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 155, M = N * N;

int n, m;
char g[N][N];
PII q[M];
int dist[N][N]; // 距离数组，保存距离

int bfs(){
    // 移动方式， 注意这里以“日”的方式移动
    int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
    int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
    int hh = 0, tt = 0;
    // 起点
    int sx, sy;
    for (int i = 0; i < n; ++ i) 
        for (int j = 0; j < m; ++ j)
            if (g[i][j] == 'K')
                sx = i, sy = j;
    
    q[0] = {sx, sy};
    
    memset(dist, -1, sizeof dist); // 初始化标记
    dist[sx][sy] = 0;
    
    while (hh <= tt){
        PII t = q[hh ++];
        
        for (int i = 0; i < 8; ++ i){
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[a][b] == '*') continue;
            if (dist[a][b] != -1) continue;
            // 判断终点，直接返回--bfs具有最短路特性，得到的距离一定是最短距离，无需额外判断
            if (g[a][b] == 'H') return dist[t.x][t.y] + 1;
            q[++ tt] = {a, b};
            dist[a][b] = dist[t.x][t.y] + 1;
        }
    }
    return -1;            
}

int main(){
    scanf("%d%d", &m, &n);
    
    for (int i = 0; i < n; ++ i) scanf("%s", g[i]);
    
    printf("%d\n", bfs());
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# BFS中的最短路模型——AcWing 1076. 迷宫问题 
# 使用库函数deque
from collections import deque

def main():
    m, n = map(int, input().split())
    g = [input() for _ in range(n)]
    dist = [[-1] * m for _ in range(n)]
    dx = [-2, -1, -1, -2, 2, 1, 1, 2]
    dy = [-1, -2, 2, 1, -1, -2, 2, 1]
    
    def bfs():
        sx, sy = 0, 0
        for i in range(n):
            for j in range(m):
                if g[i][j] == 'K':
                    sx, sy = i, j
                    break
                
        q = deque([[sx, sy]])
        dist[sx][sy] = 0
        while q:
            x, y = q.popleft()
            for i in range(8):
                a, b = x + dx[i], y + dy[i]
                if a < 0 or a >= n or b < 0 or b >= m:
                    continue
                if g[a][b] == '*':
                    continue
                if dist[a][b] != -1:
                    continue
                if g[a][b] == 'H':
                    return dist[x][y] + 1
                q.append([a, b])
                dist[a][b] = dist[x][y] + 1   
        return -1
    
    print(bfs())

if __name__ == '__main__':
    main()

3.AcWing 1100. 抓住那头牛

这里注意问题的转化，要有建图思想，转化为图的搜索问题

注意确定路径范围的上限

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// BFS中的最短路模型——AcWing 1100. 抓住那头牛
// 注意问题的转化，要有建图思想，转化为图的搜索问题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
// 注意确定路径范围的上限
const int N = 200010;

int n, k;
int q[N];
int dist[N];

int bfs(){
    int hh = 0, tt = 0;
    q[0] = n;
    
    memset(dist, -1, sizeof dist);
    dist[n] = 0;
    
    while (hh <= tt){
        int t = q[hh ++];
        
        if (t == k) return dist[k];
        // 转化为图
        // 每种移动方式表明存在边相连
        if (t + 1 < N && dist[t + 1] == -1){
            q[++ tt] = t + 1;
            dist[t + 1] = dist[t] + 1;
        }
        if (t - 1 >= 0 && dist[t - 1] == -1){
            q[++ tt] = t - 1;
            dist[t - 1] = dist[t] + 1;
        }
        if (2 * t < N && dist[2 * t] == -1){
            q[++ tt] = 2 * t;
            dist[2 * t] = dist[t] + 1;
        }
    }
    return -1;
}


int main(){
    scanf("%d%d", &n, &k);
    
    printf("%d\n", bfs());
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# BFS中的最短路模型——AcWing 1100. 抓住那头牛
# 注意问题的转化，要有建图思想，转化为图的搜索问题
# 使用库函数deque
from collections import deque

def main():
    b = 200010
    n, k = map(int, input().split())
    dist = [-1] * b
    
    def bfs():
        q = deque([n])
        dist[n] = 0
        
        while q:
            t = q.popleft()
            if (t == k):
                return dist[k]
            if (t - 1 >= 0 and dist[t - 1] == -1):
                q.append(t - 1)
                dist[t - 1] = dist[t] + 1
            if (t + 1 < b and dist[t + 1] == -1):
                q.append(t + 1)
                dist[t + 1] = dist[t] + 1
            if (2 * t < b and dist[2 * t] == -1):
                q.append(2 * t)
                dist[2 * t] = dist[t] + 1
        return -1
        
    print(bfs())
    
if __name__ == '__main__':
    main()