二维

1、岛屿数量

(1)、遇到1就DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        row = len(grid)
        col = len(grid[0])
        cnt = 0
        def dfs(i, j):
            grid[i][j] = "0"   # 设置为0，防止重复访问
            for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                tmp_i = i + x
                tmp_j = j + y
                if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
                    dfs(tmp_i, tmp_j)
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    dfs(i, j)
                    cnt += 1
        return cnt

(2)、遇到1就BFS

这两个没有什么区别，因为BFS没有终止条件，两个方法都把1遍历完了

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        from collections import deque
        if not grid: return 0
        row = len(grid)
        col = len(grid[0])
        cnt = 0
        def bfs(i, j):
            queue = deque()
            queue.appendleft((i, j))
            grid[i][j] = "0"
            while queue:
                i, j = queue.pop()
                for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                    tmp_i = i + x
                    tmp_j = j + y
                    if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
                        grid[tmp_i][tmp_j] = "0"
                        queue.appendleft((tmp_i, tmp_j))
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    bfs(i, j)
                    cnt += 1
        return cnt

2、允许对称转移的二维迷宫

多考虑一种走法

import sys
from collections import deque
def check(grid, x, y, s):
    return 0 <= x < len(grid) and 0 <= y < len(grid[0]) and 0 <= s <= 5 and grid[x][y] != '#'
def bfs(grid, x, y, s):
    n, m = len(grid), len(grid[0])
    queue = deque()
    # 事实上有了res表，不用再使用最后一位来记录结果了，而且(x,y,s)才是定义的搜索状态。但是这样写可以与不用res表的代码统一起来
    queue.append((x, y, s, 0))
    # 转移表，每个二元组表示x和y的增量
    transitions = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # s坐标后面手动控制其转移
    # 搜索状态定义为(x,y,s)，所以不再适合直接使用原矩阵记录是否已经访问
    # 这里设置res来保存搜索结果，默认值-1还可以用于判断是否已经访问
    res = [[[-1 for _ in range(5)] for _ in range(m)] for _ in range(n)]
    res[x][y][s] = 0  # 设置起点的最小时间代价为0
    while queue:
        x, y, s, t = queue.popleft()
        for i in range(5):  # 5种走法：上下左右以及对称
            if i < 4:  # 上下左右可以使用transitions统一处理
                d = transitions[i]
                nx, ny, ns, nt = x + d[0], y + d[1], s, t + 1
            else:  # 对称转移时，新坐标不是简单用一个增量加到原坐标，而是原坐标的函数，所以手动控制转移结果
                nx, ny, ns, nt = n - 1 - x, m - 1 - y, s + 1, t + 1
            if check(grid, nx, ny, ns) and res[nx][ny][ns] == -1:  # 如果下一个状态是合法的，且未访问过
                if grid[nx][ny] == 'E':  # 如果是所求的终点，返回对应的结果时间
                    return nt
                queue.append((nx, ny, ns, nt))  # 否则入队，后续再访问其邻接结点
                res[nx][ny][ns] = nt  # 记录到达该结点的最小时间，同时也表示已经访问过
    return -1
    # 起点状态，x、y为箱子的左上角格子坐标，s为已经使用飞行器的次数，t为步数/时间
    time = bfs(grid, x, y, s)
    print(time)

2.5维

1、推箱子

import sys
from collections import deque
def parse_nums(nums_str):
    return [int(x) for x in nums_str.strip().split()]
def check(grid, x, y, s):
    if x < 0 or x > len(grid) or y < 0 or y > len(grid[0]):
        return False  # 如果出界，不合法
    if grid[x][y] == '#':
        return False  # 如果箱子的坐标对应的格子是禁地，不合法
    if s == 0 and grid[x][y] == 'E':
        return False  # 如果箱子是竖着的，则箱子对应坐标是易碎也不合法
    if s == 1 and grid[x][y + 1] == '#':
        return False  # 如果箱子是左右的，则箱子的另一个格子如果是禁地也不合法
    if s == 2 and grid[x + 1][y] == '#':
        return False  # 如果箱子是上下的，则箱子的另一个格子如果是禁地也不合法
    return True
def bfs(grid, x, y, s):
    queue = deque()
    # 事实上有了res表，不用再使用最后一位来记录结果了，而且(x,y,s)才是定义的搜索状态。但是这样写可以与不用res表的代码统一起来
    queue.append((x, y, s, 0))
    # 转移表，每个三元组的前两个表示x和y的增量，第三个表示箱子姿势的转移
    transitions = [[[-2, 0, 2], [1, 0, 2], [0, -2, 1], [0, 1, 1]],  # 姿势为竖着对应的4个方向的x,y,s如何转移
                   [[-1, 0, 1], [1, 0, 1], [0, -1, 0], [0, 2, 0]],  # 姿势为左右对应的4个方向的x,y,s如何转移
                   [[-1, 0, 0], [2, 0, 0], [0, -1, 2], [0, 1, 2]]]  # 姿势为上下对应的4个方向的x,y,s如何转移
    # 搜索状态定义为(x,y,s)，所以不再适合直接使用原矩阵记录是否已经访问
    # 这里设置res来保存搜索结果，默认值-1还可以用于判断是否已经访问
    res = [[[-1 for _ in range(3)] for _ in range(len(grid[0]))] for _ in range(len(grid))]
    res[x][y][s] = 0  # 设置起点的最小时间代价为0
    while queue:
        x, y, s, t = queue.popleft()
        for d in transitions[s]:  # 用s取出转移表中对应的行
            nx, ny, ns, nt = x + d[0], y + d[1], d[2], t + 1  # 状态转移与结果记录(注意d[2]不是增量，所以ns=d[2]而不是=s+d[2])
            if check(grid, nx, ny, ns) and res[nx][ny][ns] == -1:  # 如果下一个状态是合法的，且未访问过
                if grid[nx][ny] == 'O' and ns == 0:  # 如果是所求的终点，返回对应的结果时间
                    return nt
                queue.append((nx, ny, ns, nt))  # 否则入队，后续再访问其邻接结点
                res[nx][ny][ns] = nt  # 记录到达该结点的最小时间，同时也表示已经访问过
    return -1
# 读取2维地图
for ns in sys.stdin:
    if ns == '0 0':  # 终止信号
        break
    N, M = parse_nums(ns)
    grid = []
    # 起点状态，x、y为箱子的左上角格子坐标，s为箱子姿势（0为竖着，1为左右躺着，2为上下躺着），t为步数/时间
    x, y, s, t = 0, 0, 0, 0
    first_X = True
    for i in range(N):
        row = [c for c in input()]
        if 'X' in row:
            if first_X:  # 第一次碰到X，就能判断是否为左右躺着，否则先默认竖着
                x, y, s = i, row.index('X'), 0
                if row[y + 1] == 'X':
                    s = 1
                first_X = False
            else:  # 如果碰到了两行中都有X，则是上下躺着
                s = 2
        grid.append(row)
    time = bfs(grid, x, y, s)
    print(time if time != -1 else 'Impossible')

三维

1、迷宫

import sys
from collections import deque
def parse_nums(nums_str):
    return [int(x) for x in nums_str.strip().split()]
def bfs(grid, x, y, z):
    queue = deque()
    queue.append((x, y, z, 0))
    grid[x][y][z] = '#'   # 不走回头路
    while queue:
        directions = [[1, 0, 0], [-1, 0, 0], [0, 1, 0], [0, -1, 0], [0, 0, 1], [0, 0, -1]]
        x, y, z, t = queue.popleft()
        for d in directions:    # 选择列表
            nx, ny, nz, nt = x + d[0], y + d[1], z + d[2], t + 1   # 索引
            if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) 
                and 0 <= nz < len(grid[0][0]) and grid[nx][ny][nz] != '#':   # 满足条件，加入队列
                if grid[nx][ny][nz] == 'E':
                    return nt
                queue.append((nx, ny, nz, nt))
                grid[nx][ny][nz] = '#'   # 不走回头路
    return -1
for ns in sys.stdin:
    if ns == '0 0 0':  # 终止信号
        break
    L, R, C = parse_nums(ns)   # 层数、行数、列数
    grid = []
    x, y, z = 0, 0, 0
    for i in range(L):
        level = []
        for j in range(R):
            row = [c for c in input()]
            if 'S' in row:    # 起始点
                x, y, z = i, j, row.index('S')   
            level.append(row)
        grid.append(level)
        input()  # 丢弃空行
    time = bfs(grid, x, y, z)
    print("Trapped!" if time == -1 else f"Escaped in {time} minute(s).")

进阶版 会掉血

def bfs(grid, x, y, z):
    queue = deque()
    queue.append((x, y, z, 0))
    grid[x][y][z] = '#'   # 不走回头路
    while queue:
        directions = [[1, 0, 0], [-1, 0, 0], [0, 1, 0], [0, -1, 0], [0, 0, 1], [0, 0, -1]]
        x, y, z, t, n = queue.popleft()
        for d in directions:    # 选择列表
            nx, ny, nz, nt = x + d[0], y + d[1], z + d[2], t + 1   # 索引
            if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and 0 <= nz < len(grid[0][0]) 
                and grid[nx][ny][nz] != '#' and nn>0:   # 满足条件，加入队列
                if grid[nx][ny][nz] == 'E':
                    return nt
                if grid[nx][ny][nz]=='*'":
                    nn-=1
                else:
                    nn=nn
                queue.append((nx, ny, nz, nt, nn))
                grid[nx][ny][nz] = '#'   # 不走回头路
    return -1