2 广度优先搜索（BFS）10题

前面介绍了深度优先搜索，可知 DFS 是以深度作为第一关键词的，即当碰到岔道口时总是先选择其中的一条岔路前进,而不管其他岔路,直到碰到死胡同时才返回岔道口并选择其他岔路。接下来将介绍的广度优先搜索 (Breadth FirstSearch,BFS)则是以广度为第一关键词，当碰到岔道口时,总是先依次访问从该岔道口能直接到达的所有结点,然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点，以此类推,直到所有结点都被访问为止。这就跟平静的水面中投入一颗小石子一样,水花总是以石子落水处为中心,并以同心圆的方式向外扩散至整个水面(见图 8-2),从这点来看和 DFS 那种沿着一条线前进的思路是完全不同的。

广度优先搜索 (BFS)一般由队列实现,且总是按层次的顺序进行遍历，其基本写法如下(可作模板用):

python

from collections import deque
  
def bfs(s, e):
    inq = set()
    inq.add(s)
      
    q = deque()
    q.append((0, s))

    while q:
        now, top = q.popleft() # 取出队首元素
        if top == e:
            return now # 返回需要的结果，如：步长、路径等信息

        # 将 top 的下一层结点中未曾入队的结点全部入队q，并加入集合inq设置为已入队

下面是对该模板中每一个步骤的说明,请结合代码一起看:

① 定义队列 q，并将起点(0, s)入队，0表示步长目前是0。 ② 写一个 while 循环，循环条件是队列q非空。 ③ 在 while 循环中，先取出队首元素 top。 ④ 将top 的下一层结点中所有未曾入队的结点入队，并标记它们的层号为 now 的层号加1，并加入集合inq设置为已入队。 ⑤ 返回 ② 继续循环。

为了防止走回头路，一般可以设置一个bool类型数组inq（即in queue的简写）来记录每个位置是否在BFS中已入过队。再强调一点,在BFS 中设置的 inq 数组的含义是判断结点是否已入过队，而不是结点是否已被访问。区别在于:如果设置成是否已被访问，有可能在某个结点正在队列中（但还未访问）时由于其他结点可以到达它而将这个结点再次入队，导致很多结点反复入队，计算量大大增加。因此BFS 中让每个结点只入队一次，故需要设置 inq 数组的含义为结点是否已入过队而非结点是否已被访问。

sy318: 数字操作（一维BFS）简单

https://sunnywhy.com/sfbj/8/2/318

从整数1开始，每轮操作可以选择将上轮结果加1或乘2。问至少需要多少轮操作才能达到指定整数。

输入

一个整数 $n (2 \leq n \leq 10^{5})$ ，表示需要达到的整数。

输出

输出一个整数，表示至少需要的操作轮数。

样例1

输入

输出

解释

第1轮：1 + 1 = 2

第2轮：2 + 1 =3

第3轮：3 * 2 = 6

第4轮：6 + 1 = 7

因此至少需要操作4轮。

数学思维

python

'''
2023TA-陈威宇，思路：是n的二进制表示 里面 1的个数+1的个数+0的个数-2。
如果我们将 n 的二进制表示的每一位数从左到右依次编号为 0、1、2、...，那么：

1 的个数表示需要进行加 1 的操作次数；
0 的个数表示需要进行乘 2 的操作次数；
len(l) - 2 表示操作的总次数减去初始状态的操作次数 1，即剩余的操作次数；
sum(l) + len(l) - 2 表示所有操作次数之和。
'''
n = int(input())
s = bin(n)
l = [int(i) for i in s[2:]]
print(sum(l) + len(l) - 2)

计算机思维

我们使用from collections import deque就满足要求，适用于需要频繁从队列的两端进行操作的场景，如广度优先搜索（BFS）、滑动窗口等问题。

from queue import Queue适用于多线程编程中，需要在多个线程之间安全地共享和传递数据的场景。提供线程安全的特性，内置锁机制，可以在多线程环境中安全地使用。支持阻塞操作，如 get 和 put 方法可以设置超时时间，等待队列中有数据可用或空间可用。不支持从队列两端进行操作，只能从一端进行插入和删除。

python

from collections import deque


def bfs(n):
    inq = set()
    inq.add(1)
    q = deque()
    q.append((0, 1))
    while q:
        step, front = q.popleft()
        if front == n:
            return step

        if front * 2 <= n and front * 2 not in inq:
            inq.add(front * 2)
            q.append((step + 1, front * 2))
        if front + 1 <= n and front + 1 not in inq:
            inq.add(front + 1)
            q.append((step + 1, front + 1))


n = int(input())
print(bfs(n))

sy319: 矩阵中的块简单

https://sunnywhy.com/sfbj/8/2/319

现有一个 n*m 的矩阵，矩阵中的元素为0或1。然后进行如下定义：

位置(x,y)与其上下左右四个位置 $(x, y + 1) 、 (x, y - 1) 、 (x + 1, y) 、 (x - 1, y)$ 是相邻的；
如果位置 (x1,y1) 与位置 (x2,y2) 相邻，且位置 (x2,y2) 与位置 (x3,y3) 相邻，那么称位置(x1,y1)与位置(x3,y3)也相邻；
称个数尽可能多的相邻的1构成一个“块”。

求给定的矩阵中“块”的个数。

输入

第一行两个整数 n、m（ $2 \leq n \leq 100, 2 \leq m \leq 100$ ），分别表示矩阵的行数和列数；

接下来 n 行，每行 m 个0或1（用空格隔开），表示矩阵中的所有元素。

输出

输出一个整数，表示矩阵中“块”的个数。

样例1

输入

6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

输出

解释

矩阵中的1共有4块，如下图所示。

矩阵中的块_样例.png

加保护圈，inq_set集合判断是否入过队

python

from collections import deque

# Constants
MAXD = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x, y):
    q = deque([(x, y)])
    inq_set.add((x,y))
    while q:
        front = q.popleft()
        for i in range(MAXD):
            next_x = front[0] + dx[i]
            next_y = front[1] + dy[i]
            if matrix[next_x][next_y] == 1 and (next_x,next_y) not in inq_set:
                inq_set.add((next_x, next_y))
                q.append((next_x, next_y))

# Input
n, m = map(int, input().split())
matrix=[[-1]*(m+2)]+[[-1]+list(map(int,input().split()))+[-1] for i in range(n)]+[[-1]*(m+2)]
inq_set = set()

# Main process
counter = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        if matrix[i][j] == 1 and (i,j) not in inq_set:
            bfs(i, j)
            counter += 1

# Output
print(counter)

inq 数组，结点是否已入过队

python

from collections import deque

# Constants
MAXN = 100
MAXD = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# Functions
def can_visit(x, y):
    return 0 <= x < n and 0 <= y < m and matrix[x][y] == 1 and not in_queue[x][y]

def bfs(x, y):
    q = deque([(x, y)])
    in_queue[x][y] = True
    while q:
        front = q.popleft()
        for i in range(MAXD):
            next_x = front[0] + dx[i]
            next_y = front[1] + dy[i]
            if can_visit(next_x, next_y):
                in_queue[next_x][next_y] = True
                q.append((next_x, next_y))

# Input
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
in_queue = [[False] * MAXN for _ in range(MAXN)]

# Main process
counter = 0
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1 and not in_queue[i][j]:
            bfs(i, j)
            counter += 1

# Output
print(counter)

sy320: 迷宫问题简单

https://sunnywhy.com/sfbj/8/2/320

现有一个 n*m 大小的迷宫，其中1表示不可通过的墙壁，0表示平地。每次移动只能向上下左右移动一格，且只能移动到平地上。求从迷宫左上角到右下角的最小步数。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 100, 2 \leq m \leq 100)$ ，分别表示迷宫的行数和列数；

接下来 n 行，每行 m 个整数（值为0或1），表示迷宫。

输出

输出一个整数，表示最小步数。如果无法到达，那么输出-1。

样例1

输入

输出

解释: 假设左上角坐标是(1,1)，行数增加的方向为增长的方向，列数增加的方向为增长的方向。

可以得到从左上角到右下角的前进路线：(1,1)=>(2,1)=>(2,2)=>(2,3)=>(3,3)。

因此最少需要4步。

样例2

输入

输出

-1

解释: 显然从左上角无法到达右下角。

加保护圈，inq_set集合判断是否入过队

python

from collections import deque

# 声明方向变化的数组，代表上下左右移动
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x, y, n, m, maze):
    q = deque()
    q.append((0, (x, y)))  # (step, (x, y))
    inq_set = set()
    inq_set.add((x, y))
    
    while q:
        step, (cur_x, cur_y) = q.popleft()
        
        if cur_x == n and cur_y == m:
            return step
        
        for direction in range(4):
            next_x = cur_x + dx[direction]
            next_y = cur_y + dy[direction]
            
            if maze[next_x][next_y] == 0 and (next_x, next_y) not in inq_set:
                inq_set.add((next_x, next_y))
                q.append((step + 1, (next_x, next_y)))
    
    return -1

if __name__ == '__main__':
    n, m = map(int, input().split())
    
    # 初始化迷宫，增加边界
    maze = [[-1] * (m + 2)] + [[-1] + list(map(int, input().split())) + [-1] for _ in range(n)] + [[-1] * (m + 2)]
    
    step = bfs(1, 1, n, m, maze)
    print(step)

inq 数组，结点是否已入过队

python

from collections import deque

# 声明方向变化的数组，代表上下左右移动
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 检查是否可以访问位置 (x, y)
def can_visit(x, y):
    return 0 <= x < n and 0 <= y < m and maze[x][y] == 0 and not in_queue[x][y]

# BFS函数 实现广度优先搜索
def bfs(x, y):
    q = deque()
    q.append((0, (x, y)))
    in_queue[x][y] = True
    while q:
        for _ in range(len(q)):
            step, (cur_x, cur_y) = q.popleft()
            if cur_x == n - 1 and cur_y == m - 1:
                return step
            for direction in range(4):
                next_x = cur_x + dx[direction]
                next_y = cur_y + dy[direction]
                if can_visit(next_x, next_y):
                    in_queue[next_x][next_y] = True
                    q.append((step + 1, (next_x, next_y)))
    return -1

# 主函数
if __name__ == '__main__':
    # 读取 n 和 m
    n, m = map(int, input().split())
    maze = []
    in_queue = [[False] * m for _ in range(n)]

    # 填充迷宫和访问状态数组
    for i in range(n):
        maze.append(list(map(int, input().split())))

    # 执行BFS并输出步数
    step = bfs(0, 0)
    print(step)

sy321: 迷宫最短路径中等

https://sunnywhy.com/sfbj/8/2/321

现有一个 n*m 大小的迷宫，其中1表示不可通过的墙壁，0表示平地。每次移动只能向上下左右移动一格，且只能移动到平地上。假设左上角坐标是(1,1)，行数增加的方向为增长的方向，列数增加的方向为增长的方向，求从迷宫左上角到右下角的最少步数的路径。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 100, 2 \leq m \leq 100)$ ，分别表示迷宫的行数和列数；

接下来 n 行，每行 m 个整数（值为0或1），表示迷宫。

输出

从左上角的坐标开始，输出若干行（每行两个整数，表示一个坐标），直到右下角的坐标。

数据保证最少步数的路径存在且唯一。

样例1

输入

输出

解释

假设左上角坐标是(1,)，行数增加的方向为增长的方向，列数增加的方向为增长的方向。

可以得到从左上角到右下角的最少步数的路径为：(1,1)=>(2,1)=>(2,2)=>(2,3)=>(3,3)。

in_queue 数组，结点是否已入过队

python

from collections import deque

# 声明方向变化的数组，代表上下左右移动
MAX_DIRECTIONS = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def is_valid_move(x, y, n, m, maze, in_queue):
    return 0 <= x < n and 0 <= y < m and maze[x][y] == 0 and (x, y) not in in_queue

def bfs(start_x, start_y, n, m, maze):
    queue = deque()
    queue.append((start_x, start_y))
    
    in_queue = set()
    prev = [[(-1, -1)] * m for _ in range(n)]
    
    in_queue.add((start_x, start_y))
    while queue:
        x, y = queue.popleft()
        if x == n - 1 and y == m - 1:
            return prev
        for i in range(MAX_DIRECTIONS):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if is_valid_move(next_x, next_y, n, m, maze, in_queue):
                prev[next_x][next_y] = (x, y)
                in_queue.add((next_x, next_y))
                queue.append((next_x, next_y))
    return None

def print_path(prev, end_pos):
    path = []
    while end_pos != (-1, -1):
        path.append(end_pos)
        end_pos = prev[end_pos[0]][end_pos[1]]
    path.reverse()
    for pos in path:
        print(pos[0] + 1, pos[1] + 1)

if __name__ == '__main__':
    n, m = map(int, input().split())
    maze = [list(map(int, input().split())) for _ in range(n)]
    
    prev = bfs(0, 0, n, m, maze)
    if prev:
        print_path(prev, (n - 1, m - 1))
    else:
        print("No path found")

python

from collections import deque
import sys

def main():
    data = iter(sys.stdin.read().splitlines())
    m, n = map(int, next(data).split())
    grid = [list(map(int, next(data).split())) for _ in range(m)]
    
    # 方向映射：(dx, dy) -> char
    directions = [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]
    
    # BFS 队列：(x, y)
    q = deque()
    q.append((0, 0))
    grid[0][0] = 1  # 入队即标记
    
    # 记录每个点的父节点和进入方向
    parent = {}
    parent[(0, 0)] = (None, None)  # (parent_coord, move_char)

    found = False
    while q:
        x, y = q.popleft()
        if x == m - 1 and y == n - 1:
            found = True
            break
        for dx, dy, move in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
                grid[nx][ny] = 1  # 立即标记，防止重复入队
                parent[(nx, ny)] = ((x, y), move)
                q.append((nx, ny))
    
    if not found:
        # 如果题目保证有解，可省略；否则应处理无解情况
        return

    # 回溯路径
    path_moves = []
    curr = (m - 1, n - 1)
    while parent[curr][0] is not None:
        _, move = parent[curr]
        path_moves.append(move)
        curr = parent[curr][0]
    
    path_moves.reverse()  # 从起点到终点

    # 输出路径（1-indexed）
    x, y = 1, 1
    print(f"{x} {y}")
    for move in path_moves:
        if move == 'u':
            x -= 1
        elif move == 'd':
            x += 1
        elif move == 'l':
            y -= 1
        elif move == 'r':
            y += 1
        print(f"{x} {y}")

if __name__ == "__main__":
    main()

sy322: 跨步迷宫中等

https://sunnywhy.com/sfbj/8/2/322

现有一个n*m大小的迷宫，其中1表示不可通过的墙壁，0表示平地。每次移动只能向上下左右移动一格或两格（两格为同向），且只能移动到平地上（不允许跨越墙壁）。求从迷宫左上角到右下角的最小步数（假设移动两格时算作一步）。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 100, 2 \leq m \leq 100)$ ，分别表示迷宫的行数和列数；

接下来n行，每行m个整数（值为0或1），表示迷宫。

输出

输出一个整数，表示最小步数。如果无法到达，那么输出-1。

样例1

输入

输出

解释

假设左上角坐标是，行数增加的方向为增长的方向，列数增加的方向为增长的方向。

可以得到从左上角到右下角的前进路线：=>=>=>。

因此最少需要3步。

样例2

输入

输出

-1

解释

显然从左上角无法到达右下角。

python

from collections import deque

# 声明方向变化的数组，代表上下左右及四个斜向移动
MAXD = 8
dx = [0, 0, 0, 0, 1, -1, 2, -2]
dy = [1, -1, 2, -2, 0, 0, 0, 0]

def canVisit(x, y, n, m, maze, in_queue):
    return 0 <= x < n and 0 <= y < m and maze[x][y] == 0 and (x, y) not in in_queue

def bfs(start_x, start_y, n, m, maze):
    q = deque()
    q.append((0, start_x, start_y))  # (step, x, y)
    in_queue = {(start_x, start_y)}
    
    while q:
        step, x, y = q.popleft()
        
        if x == n - 1 and y == m - 1:
            return step
        
        for i in range(MAXD):
            next_x = x + dx[i]
            next_y = y + dy[i]
            next_half_x = x + dx[i] // 2
            next_half_y = y + dy[i] // 2
            
            if canVisit(next_x, next_y, n, m, maze, in_queue) and maze[next_half_x][next_half_y] == 0:
                in_queue.add((next_x, next_y))
                q.append((step + 1, next_x, next_y))
    
    return -1

if __name__ == '__main__':
    n, m = map(int, input().split())
    maze = [list(map(int, input().split())) for _ in range(n)]
    
    step = bfs(0, 0, n, m, maze)
    print(step)

sy323: 字符迷宫中等

https://sunnywhy.com/sfbj/8/2/323

现有一个n*m大小的迷宫，其中*表示不可通过的墙壁，.表示平地。每次移动只能向上下左右移动一格，且只能移动到平地上。求从起点S到终点T的最小步数。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 100, 2 \leq m \leq 100)$ ，分别表示迷宫的行数和列数；

接下来n行，每行一个长度为m的字符串，表示迷宫。

输出

输出一个整数，表示最小步数。如果无法从S到达T，那么输出-1。

样例1

输入

5 5
.....
.*.*.
.*S*.
.***.
...T*

输出

解释

假设左上角坐标是(1,1)，行数增加的方向为x增长的方向，列数增加的方向为y增长的方向。

起点的坐标为(3,3)，终点的坐标为(5,4)。

可以得到从S到T的前进路线：(3,3)=>(2,3)=>(1,3)=>(1,2)=>(1,1)=>(2,1)=>(3,1)=>(4,1)=>(5,1)=>(5,2)=>(5,3)=>(5,4)。

样例2

输入

5 5
.....
.*.*.
.*S*.
.***.
..*T*

输出

-1

解释

显然终点T被墙壁包围，无法到达。

python

from collections import deque

# 声明方向变化的数组，代表上下左右移动
MAXD = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def canVisit(x, y, n, m, maze, in_queue):
    return 0 <= x < n and 0 <= y < m and maze[x][y] == 0 and (x, y) not in in_queue

def BFS(start, target, n, m, maze):
    q = deque([(0, start)])  # (step, (x, y))
    in_queue = {start}
    
    while q:
        step, (x, y) = q.popleft()
        
        if (x, y) == target:
            return step
        
        for i in range(MAXD):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if canVisit(next_x, next_y, n, m, maze, in_queue):
                in_queue.add((next_x, next_y))
                q.append((step + 1, (next_x, next_y)))
    
    return -1

if __name__ == '__main__':
    n, m = map(int, input().split())
    maze = []
    start, target = None, None
    
    for i in range(n):
        row = input().strip()
        maze_row = []
        for j in range(m):
            if row[j] == '.':
                maze_row.append(0)
            elif row[j] == '*':
                maze_row.append(1)
            elif row[j] == 'S':
                start = (i, j)
                maze_row.append(0)
            elif row[j] == 'T':
                target = (i, j)
                maze_row.append(0)
        maze.append(maze_row)
    
    if start is None or target is None:
        print(-1)
    else:
        step = BFS(start, target, n, m, maze)
        print(step)

sy324: 多终点迷宫问题中等

https://sunnywhy.com/sfbj/8/2/324

现有一个 n*m 大小的迷宫，其中1表示不可通过的墙壁，0表示平地。每次移动只能向上下左右移动一格，且只能移动到平地上。求从迷宫左上角到迷宫中每个位置的最小步数。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 100, 2 \leq m \leq 100)$ ，分别表示迷宫的行数和列数；

接下来n行，每行m个整数（值为0或1），表示迷宫。

输出

输出n行m列个整数，表示从左上角到迷宫中每个位置需要的最小步数。如果无法到达，那么输出-1。注意，整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

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

解释

假设左上角坐标是，行数增加的方向为增长的方向，列数增加的方向为增长的方向。

可以得到从左上角到所有点的前进路线：=>=>或=>=>。

左下角的三个位置无法到达。

python

from collections import deque
import sys

INF = sys.maxsize
MAXD = 4

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def canVisit(x, y, n, m, maze, in_queue):
    return 0 <= x < n and 0 <= y < m and maze[x][y] == 0 and (x, y) not in in_queue

def BFS(start_x, start_y, n, m, maze):
    minStep = [[-1] * m for _ in range(n)]
    q = deque([(0, start_x, start_y)])  # (step, x, y)
    in_queue = {(start_x, start_y)}
    minStep[start_x][start_y] = 0
    
    while q:
        step, x, y = q.popleft()
        
        for i in range(MAXD):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if canVisit(next_x, next_y, n, m, maze, in_queue):
                in_queue.add((next_x, next_y))
                minStep[next_x][next_y] = step + 1
                q.append((step + 1, next_x, next_y))
    
    return minStep

n, m = map(int, input().split())
maze = []

for _ in range(n):
    maze.append(list(map(int, input().split())))

minStep = BFS(0, 0, n, m, maze)
for i in range(n):
    print(' '.join(map(str, minStep[i])))

sy325: 迷宫问题-传送点中等

https://sunnywhy.com/sfbj/8/2/325

现有一个n*m大小的迷宫，其中1表示不可通过的墙壁，0表示平地，2表示传送点。每次移动只能向上下左右移动一格，且只能移动到平地或传送点上。当位于传送点时，可以选择传送到另一个2处（传送不计入步数），也可以选择不传送。求从迷宫左上角到右下角的最小步数。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 100, 2 \leq m \leq 100)$ ，分别表示迷宫的行数和列数；

接下来n行，每行m个整数（值为0或1或2），表示迷宫。数据保证有且只有两个2，且传送点不会在起始点出现。

输出

输出一个整数，表示最小步数。如果无法到达，那么输出-1。

样例1

输入

输出

解释

假设左上角坐标是，行数增加的方向为增长的方向，列数增加的方向为增长的方向。

可以得到从左上角到右下角的前进路线：=>=>=>=>=>，其中=>属于传送，不计入步数。

因此最少需要4步。

样例2

输入

输出

-1

解释

显然从左上角无法到达右下角。

python

from collections import deque

# 读取输入
size = list(map(int, input().split()))
rows, cols = size[0], size[1]
mymap = []
portals = []  # 存所有传送门坐标

for i in range(rows):
    row = list(map(int, input().split()))
    mymap.append(row)
    for j, val in enumerate(row):
        if val == 2:
            portals.append((i, j))

# BFS
visited = [[False] * cols for _ in range(rows)]
queue = deque()
queue.append((0, 0, 0))
visited[0][0] = True

# 标记是否已经“激活”传送网络（即是否已经把所有 portal 加入过队列）
portals_used = False

while queue:
    x, y, dist = queue.popleft()
    
    # 到达终点
    if x == rows - 1 and y == cols - 1:
        print(dist)
        exit(0)
    
    # 如果当前是传送门，且还没广播过所有传送门
    if mymap[x][y] == 2 and not portals_used:
        portals_used = True
        for px, py in portals:
            if not visited[px][py]:
                visited[px][py] = True
                queue.append((px, py, dist))  # 传送不增加步数
    
    # 四方向移动
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < rows and 0 <= ny < cols:
            if not visited[nx][ny] and mymap[nx][ny] != 1:
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))

# 无法到达
print(-1)

将 transVector 中的第一个位置映射到第二个位置，并将第二个位置映射到第一个位置。这样，就建立了传送门的双向映射关系。

在 BFS 函数中，当遇到传送门时，通过映射表 transMap 找到传送门的另一侧位置，并将其加入队列，以便继续进行搜索。

python

from collections import deque

MAXD = 4

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def canVisit(x, y, n, m, maze, in_queue):
    return 0 <= x < n and 0 <= y < m and (maze[x][y] == 0 or maze[x][y] == 2) and (x, y) not in in_queue

def BFS(start_x, start_y, n, m, maze, transMap):
    q = deque([(0, start_x, start_y)])  # (step, x, y)
    in_queue = {(start_x, start_y)}

    while q:
        step, x, y = q.popleft()

        if x == n - 1 and y == m - 1:
            return step

        for i in range(MAXD):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if canVisit(next_x, next_y, n, m, maze, in_queue):
                in_queue.add((next_x, next_y))
                q.append((step + 1, next_x, next_y))

                if maze[next_x][next_y] == 2:
                    trans_position = transMap.get((next_x, next_y))
                    if trans_position:
                        in_queue.add(trans_position)
                        q.append((step + 1, trans_position[0], trans_position[1]))

    return -1

n, m = map(int, input().split())
maze = []
transMap = {}
transVector = []

for i in range(n):
    row = list(map(int, input().split()))
    maze.append(row)

    if 2 in row:
        for j, val in enumerate(row):
            if val == 2:
                transVector.append((i, j))

        if len(transVector) == 2:
            transMap[transVector[0]] = transVector[1]
            transMap[transVector[1]] = transVector[0]
            transVector = []  # 清空 transVector 以便处理下一对传送点

if transVector:
    print("Error: Unpaired teleportation point found.")
    exit(1)

step = BFS(0, 0, n, m, maze, transMap)
print(step)

sy326: 中国象棋-马-无障碍中等

https://sunnywhy.com/sfbj/8/2/326

现有一个n*m大小的棋盘，在棋盘的第行第列的位置放置了一个棋子，其他位置都未放置棋子。棋子的走位参照中国象棋的“马”。求该棋子到棋盘上每个位置的最小步数。

注：中国象棋中“马”的走位为“日”字形，如下图所示。

输入

四个整数 $n 、 m 、 x 、 y (2 \leq n \leq 100, 2 \leq m \leq 100, 1 \leq x \leq n, 1 \leq y \leq m)$ ，分别表示棋盘的行数和列数、棋子的所在位置。

输出

输出行列个整数，表示从棋子到棋盘上每个位置需要的最小步数。如果无法到达，那么输出-1。注意，整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

3 3 2 1

输出

3 2 1
0 -1 4
3 2 1

解释

共3行3列，“马”在第2行第1列的位置，由此可得“马”能够前进的路线如下图所示。

python

from collections import deque

MAXD = 8

dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]


def canVisit(x, y, n, m, in_queue):
    return 0 <= x < n and 0 <= y < m and (x, y) not in in_queue


def BFS(start_x, start_y, n, m):
    minStep = [[-1] * m for _ in range(n)]
    queue = deque([(0, start_x, start_y)])  # (step, x, y)
    in_queue = {(start_x, start_y)}
    minStep[start_x][start_y] = 0

    while queue:
        step, x, y = queue.popleft()

        for i in range(MAXD):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if canVisit(next_x, next_y, n, m, in_queue):
                in_queue.add((next_x, next_y))
                minStep[next_x][next_y] = step + 1
                queue.append((step + 1, next_x, next_y))

    return minStep


n, m, x, y = map(int, input().split())

minStep = BFS(x - 1, y - 1, n, m)
for row in minStep:
    print(' '.join(map(str, row)))

sy327: 中国象棋-马-有障碍中等

https://sunnywhy.com/sfbj/8/2/327

现有一个大小的棋盘，在棋盘的第行第列的位置放置了一个棋子，其他位置中的一部分放置了障碍棋子。棋子的走位参照中国象棋的“马”（障碍棋子将成为“马脚”）。求该棋子到棋盘上每个位置的最小步数。

注1：中国象棋中“马”的走位为“日”字形，如下图所示。

中国象棋-马-有障碍_题目描述1.png

注2：与“马”直接相邻的棋子会成为“马脚”，“马”不能往以“马”=>“马脚”为长边的方向前进，如下图所示。

中国象棋-马-有障碍_题目描述2.png

输入

第一行四个整数 $n 、 m 、 x 、 y (2 \leq n \leq 100, 2 \leq m \leq 100, 1 \leq x \leq n, 1 \leq y \leq m)$ ，分别表示棋盘的行数和列数、棋子的所在位置；

第二行一个整数 $k （ 1 \leq k \leq 10 ）$ ，表示障碍棋子的个数；

接下来k行，每行两个整数 $x_{i} 、 y_{i} （ 1 \leq x_{i} \leq n, 1 \leq y_{i} \leq m ）$ ，表示第i个障碍棋子的所在位置。数据保证不存在相同位置的障碍棋子。

输出

输出n行m列个整数，表示从棋子到棋盘上每个位置需要的最小步数。如果无法到达，那么输出-1。注意，整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

3 3 2 1
1
1 2

输出

3 -1 1
0 -1 -1
-1 2 1

解释

共3行3列，“马”在第2行第1列的位置，障碍棋子在第1行第2列的位置，由此可得“马”能够前进的路线如下图所示。

python

from collections import deque

MAXD = 8
dx = [-2, -2, -1, 1, 2, 2, 1, -1]
dy = [1, -1, -2, -2, -1, 1, 2, 2]


def canVisit(x, y):
    return 0 <= x < n and 0 <= y < m and (x, y) not in isBlock and (x, y) not in in_queue


def BFS(start_x, start_y):
    minStep = [[-1] * m for _ in range(n)]
    queue = deque([(0, start_x, start_y)])  # (step, x, y)
    in_queue.add((start_x, start_y))
    minStep[start_x][start_y] = 0

    while queue:
        step, x, y = queue.popleft()

        wx, wy = [-1, 0, 1, 0], [0, -1, 0, 1]
        for i in range(MAXD):
            nextX = x + dx[i]
            nextY = y + dy[i]
            footX, footY = x + wx[i//2], y + wy[i//2]

            if canVisit(nextX, nextY) and (footX, footY) not in isBlock:
                in_queue.add((nextX, nextY))
                minStep[nextX][nextY] = step + 1
                queue.append((step + 1, nextX, nextY))

    return minStep


n, m, x, y = map(int, input().split())
in_queue = set()
isBlock = {}

k = int(input())
for _ in range(k):
    blockX, blockY = map(int, input().split())
    isBlock[(blockX - 1, blockY - 1)] = True

minStep = BFS(x - 1, y - 1)

for row in minStep:
    print(' '.join(map(str, row)))

2 广度优先搜索（BFS）10题 ​

sy318: 数字操作（一维BFS）简单 ​

数学思维 ​

计算机思维 ​

sy319: 矩阵中的块 简单 ​

加保护圈，inq_set集合判断是否入过队 ​

inq 数组，结点是否已入过队 ​

sy320: 迷宫问题 简单 ​

加保护圈，inq_set集合判断是否入过队 ​

inq 数组，结点是否已入过队 ​

sy321: 迷宫最短路径 中等 ​

sy322: 跨步迷宫 中等 ​

sy323: 字符迷宫 中等 ​

sy324: 多终点迷宫问题 中等 ​

sy325: 迷宫问题-传送点 中等 ​

sy326: 中国象棋-马-无障碍 中等 ​

sy327: 中国象棋-马-有障碍 中等 ​

2 广度优先搜索（BFS）10题

sy318: 数字操作（一维BFS）简单

数学思维

计算机思维

sy319: 矩阵中的块简单

加保护圈，inq_set集合判断是否入过队

inq 数组，结点是否已入过队

sy320: 迷宫问题简单

加保护圈，inq_set集合判断是否入过队

inq 数组，结点是否已入过队

sy321: 迷宫最短路径中等

sy322: 跨步迷宫中等

sy323: 字符迷宫中等

sy324: 多终点迷宫问题中等

sy325: 迷宫问题-传送点中等

sy326: 中国象棋-马-无障碍中等

sy327: 中国象棋-马-有障碍中等