225小S的黑白块迷宫

问题描述

在一个 n×m 的网格迷宫中，初始位置在左上角 (1,1)，目标是到达右下角 (n,m)。每个格子可以是黑色（表示为 1）或者白色（表示为 0）。移动时可以向上、下、左、右四个方向移动，但不能走出迷宫的边界。要求在移动过程中经过的黑色格子尽可能少。

解题思路

本题可以使用广度优先搜索（BFS）算法来解决。由于需要最小化经过的黑色格子数量，可以将其视为带权图的最短路径问题，其中白色格子的权重为 0，黑色格子的权重为 1。

BFS 遍历：

• 从队列中取出当前格子 (x, y, d)。
• 如果当前的黑色格子数 d 大于已记录的最小值，跳过此格子。
• 遍历四个可能的移动方向，计算新位置 (nx, ny)。
• 如果新位置在迷宫范围内，并且通过当前路径到达新位置的黑色格子数更少，则更新 dis[nx][ny]并将新位置加入队列。

代码实现

from collections import deque
dx, dy = [0, 1, 0, -1, 1, -1, 1, -1], [1, 0, -1, 0, -1, -1, 1, 1]

def solution(n: int, m: int, grid: list) -> int:
    q = deque([(0, 0, 0)])
    dis = [[n * m] * m for _ in range(n)]
    dis[0][0] = grid[0][0]
    while q:
        x, y, d = q.popleft()
        if d > dis[x][y]:
            continue
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if dis[nx][ny] > dis[x][y] + grid[nx][ny]:
                    dis[nx][ny] = dis[x][y] + grid[nx][ny]
                    q.append((nx, ny, dis[nx][ny]))
    return dis[-1][-1]



if __name__ == '__main__':
    print(solution(5, 3, [[0, 1, 0], [0, 1, 1], [0, 1, 0], [1, 0, 0], [1, 0, 0]]) == 1)
    print(solution(4, 4, [[0, 0, 1, 0], [1, 0, 1, 0], [1, 0, 0, 0], [1, 1, 1, 0]]) == 0)
    print(solution(3, 3, [[0, 0, 0], [1, 1, 0], [1, 1, 0]]) == 0)

时间复杂度

该算法的时间复杂度为 O(nm)，其中 n 和 m 分别是网格的行数和列数。每个格子最多被访问一次。

空间复杂度

空间复杂度为 O(nm)，用于存储 dis 数组和队列中的元素。