讨论/题目交流/🏆 第 181 场力扣周赛/
🏆 第 181 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 按既定顺序创建目标数组
4 分 - 四因数
5 分 - 检查网格中是否存在有效路径
6 分 - 最长快乐前缀

展开讨论
力扣 (LeetCode)发起于 2020-03-22

BFS解决第三题(而且BFS可以保证这条到达重点的路是最短的)
主要是要定义好当前所在单元格可以走的方向
举个栗子:
如果当前单元格为(i, j),且grid[i][j] = 1,那么它就只能左右移动,
1、选择向右移动(i, j + 1),它右边的单元格必须有一条由左出发的通道,即左右,左上和左下街道(1, 3, 5)
2、选择向左移动(i, j - 1),它左边的单元格必须有一条由右出发的通道,即右左,右上,右下街道(1, 4, 6)
所以定义dirs[1] = [(0, 1), (0, -1)]
而valids[1] = [(1, 3, 5), (1, 4, 6)]
以此类推,定义好dirs和valids后,剩余步骤就是bfs的常规步骤啦

class Solution(object):
    def hasValidPath(self, grid):
        dirs = {1: [(0, 1), (0, -1)], 2: [(1, 0), (-1, 0)],
                3: [(0, -1), (1, 0)], 4: [(0, 1), (1, 0)],
                5: [(0, -1), (-1, 0)], 6: [(-1, 0), (0, 1)]}
        valids = {1: [[1, 3, 5], [1, 4, 6]], 2: [[2, 5, 6], [2, 3, 4]],
                  3: [[1, 4, 6], [2, 5, 6]], 4: [[1, 3, 5], [2, 5, 6]],
                  5: [[1, 4, 6], [2, 3, 4]], 6: [[2, 3, 4], [1, 3, 5]]}
        queue = [(0, 0)]
        rows, cols = len(grid), len(grid[0])
        visited = [[False for _ in range(cols)] for _ in range(rows)]
        while queue:
            i, j = queue[0]
            del queue[0]

            if i == rows - 1 and j == cols - 1:
                return True

            num = grid[i][j]

            for index, (di, dj) in enumerate(dirs[num]):
                ni, nj = di + i, dj + j
                if ni < 0 or nj < 0 or ni >= rows or nj >= cols:
                    continue
                if visited[ni][nj]:
                    continue
                if grid[ni][nj] not in valids[num][index]:
                    continue
                if ni == rows - 1 and nj == cols - 1:
                    return True
                visited[ni][nj] = True
                queue.append((ni, nj))

        return False
1
展开全部 41 讨论