leetcode/lc/994/

[giscus[bot]]

leetcode/lc/994/

多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

https://doocs.github.io/leetcode/lc/994/

[lazyJLBL]

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ans = -1
        q = []
        fresh = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append([i,j])
                elif grid[i][j] == 1:
                    fresh += 1
        def bfs(q, grid, ans, fresh):
            q1 = q
            q = []
            ans += 1
            for a in q1:
                if a[0] - 1 >= 0 and grid[a[0] - 1][a[1]] == 1:
                    q.append([a[0] - 1, a[1]])
                    grid[a[0] - 1][a[1]] = 2
                    fresh -= 1
                if a[1] - 1 >= 0 and grid[a[0]][a[1] - 1] == 1:
                    q.append([a[0], a[1] - 1])
                    grid[a[0]][a[1] - 1] = 2
                    fresh -= 1
                if a[0] + 1 < m and grid[a[0] + 1][a[1]] == 1:
                    q.append([a[0] + 1, a[1]])
                    grid[a[0] + 1][a[1]] = 2
                    fresh -= 1
                if a[1] + 1 < n and grid[a[0]][a[1] + 1] == 1:
                    q.append([a[0], a[1] + 1])
                    grid[a[0]][a[1] + 1] = 2
                    fresh -= 1
            return q
        while q:
            bfs(q,grid,ans,fresh)
        if fresh != 0:
            return -1
        else:
            return max(ans,0)

大佬你好，为什么这样就一直超时呀，是因为我的bfs有问题吗

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ans = -1
        q = []
        fresh = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append([i,j])
                elif grid[i][j] == 1:
                    fresh += 1
        def bfs(q, grid, ans, fresh):
            q1 = q
            q = []
            ans += 1
            for a in q1:
                if a[0] - 1 >= 0 and grid[a[0] - 1][a[1]] == 1:
                    q.append([a[0] - 1, a[1]])
                    grid[a[0] - 1][a[1]] = 2
                    fresh -= 1
                if a[1] - 1 >= 0 and grid[a[0]][a[1] - 1] == 1:
                    q.append([a[0], a[1] - 1])
                    grid[a[0]][a[1] - 1] = 2
                    fresh -= 1
                if a[0] + 1 < m and grid[a[0] + 1][a[1]] == 1:
                    q.append([a[0] + 1, a[1]])
                    grid[a[0] + 1][a[1]] = 2
                    fresh -= 1
                if a[1] + 1 < n and grid[a[0]][a[1] + 1] == 1:
                    q.append([a[0], a[1] + 1])
                    grid[a[0]][a[1] + 1] = 2
                    fresh -= 1
            return q
        while q:
            q1 = q
            q = []
            ans += 1
            for a in q1:
                if a[0] - 1 >= 0 and grid[a[0] - 1][a[1]] == 1:
                    q.append([a[0] - 1, a[1]])
                    grid[a[0] - 1][a[1]] = 2
                    fresh -= 1
                if a[1] - 1 >= 0 and grid[a[0]][a[1] - 1] == 1:
                    q.append([a[0], a[1] - 1])
                    grid[a[0]][a[1] - 1] = 2
                    fresh -= 1
                if a[0] + 1 < m and grid[a[0] + 1][a[1]] == 1:
                    q.append([a[0] + 1, a[1]])
                    grid[a[0] + 1][a[1]] = 2
                    fresh -= 1
                if a[1] + 1 < n and grid[a[0]][a[1] + 1] == 1:
                    q.append([a[0], a[1] + 1])
                    grid[a[0]][a[1] + 1] = 2
                    fresh -= 1
        if fresh != 0:
            return -1
        else:
            return max(ans,0)

这两个版本的区别就是有没有把函数bfs放在while循环里面，为什么第一个会超时呢

[yanglbme]

bfs return 出来的 q，要赋值给原来的 q。然后 ans, fresh 使用 nonlocal 引用。我修改了一下你的代码，现在可以了，你看下。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ans = -1
        q = []
        fresh = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append([i,j])
                elif grid[i][j] == 1:
                    fresh += 1
        def bfs(q, grid):
            q1 = q
            q = []
            # ans, fresh 引用
            nonlocal ans, fresh
            ans += 1
            for a in q1:
                if a[0] - 1 >= 0 and grid[a[0] - 1][a[1]] == 1:
                    q.append([a[0] - 1, a[1]])
                    grid[a[0] - 1][a[1]] = 2
                    fresh -= 1
                if a[1] - 1 >= 0 and grid[a[0]][a[1] - 1] == 1:
                    q.append([a[0], a[1] - 1])
                    grid[a[0]][a[1] - 1] = 2
                    fresh -= 1
                if a[0] + 1 < m and grid[a[0] + 1][a[1]] == 1:
                    q.append([a[0] + 1, a[1]])
                    grid[a[0] + 1][a[1]] = 2
                    fresh -= 1
                if a[1] + 1 < n and grid[a[0]][a[1] + 1] == 1:
                    q.append([a[0], a[1] + 1])
                    grid[a[0]][a[1] + 1] = 2
                    fresh -= 1
            return q
        while q:
            # 更新 q
            q = bfs(q,grid)
        if fresh != 0:
            return -1
        else:
            return max(ans,0)

[lazyJLBL]

okok,感谢大佬