数据结构与算法——广度搜索BFS_zeroes_pos = [(i, j) for i in range(m) for j in ra

模板

542.01矩阵

class Solution:
    def updateMatrix(self, matrix) :
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
        # 将所有的 0 添加进初始队列中
        q = collections.deque(zeroes_pos)
        print(q)
        seen = set(zeroes_pos)
        print(seen)

        # 广度优先搜索
        while q:
            i, j = q.popleft()
            for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:
                    dp[ni][nj] = dp[i][j] + 1
                    q.append((ni, nj))
                    seen.add((ni, nj))
        return dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

529.扫雷游戏

#Bfs
class Solution:
    def updateBoard(self, board, click) :
        i, j = click
        row, col = len(board), len(board[0])
        if board[i][j] == "M":
            board[i][j] = "X"
            return board

        # 计算空白块周围的地雷
        def cal(i, j):
            res = 0
            for x in [1, -1, 0]:
                for y in [1, -1, 0]:
                    if x == 0 and y == 0: continue
                    if 0 <= i + x < row and 0 <= j + y < col and board[i + x][j + y] == "M": res += 1
            return res

        def bfs(i, j):
            queue = collections.deque([[i, j]])
            print(queue)
            while queue:
                i, j = queue.pop()
                num = cal(i, j)
                if num > 0:
                    board[i][j] = str(num)
                    continue
                    
                board[i][j] = "B"

                for x in [-1, 1, 0]:
                    for y in [-1, 1, 0]:
                        if x == 0 and y == 0: continue
                        nxt_i, nxt_j = i + x, j + y
                        if 0 <= nxt_i < row and 0 <= nxt_j < col and board[nxt_i][nxt_j] == "E":
                            queue.appendleft([nxt_i, nxt_j])
                            board[nxt_i][nxt_j] = "B"
        bfs(i, j)
        return board
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

2146.价格范围内最高排名的k样物品

class Solution:
    def highestRankedKItems(self, grid, pricing, start, k):
        ans = []
        m, n = len(grid), len(grid[0])
        low, high = pricing
        s_x, s_y = start
        vis = {(s_x, s_y)}
        q = [(s_x, s_y)]
        dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))
        #优先级1，步数优先，先递归的步数小
        while q:  # 分层 BFS
            # 优先级2，同一步数，数值小优先
            q.sort(key=lambda p: (grid[p[0]][p[1]], p))
            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)
            if len(ans) >= k:
                return ans[:k]
            tmp = q
            q = []
            #更新搜索空间
            for p in tmp:
                for d in dirs:
                    x, y = p[0] + d[0], p[1] + d[1]
                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:
                        vis.add((x, y))
                        q.append((x, y))
        return ans
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