542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
具体题目链接

Python

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        mat_r,mat_c=len(mat),len(mat[0])
        dist_list=[[0]*mat_c for _ in range(mat_r)]#初始化距离列表
        zeros_list=[(i,j) for j in range(mat_c) for i in range(mat_r) if mat[i][j]==0]
        que=collections.deque(zeros_list)
        seen=set(zeros_list)#采用集合是因为集合是字典形式，速度快。
        while que:
            r1,c1=que.popleft()
            for r2, c2 in [(r1 - 1, c1), (r1 + 1, c1), (r1, c1 - 1), (r1, c1 + 1)]:
                if 0 <= r2 < mat_r and 0 <= c2 < mat_c and (r2, c2) not in seen:
                    dist_list[r2][c2] = dist_list[r1][c1] + 1#距离储存
                    que.append((r2, c2))#增加到队列中
                    seen.add((r2, c2))
        return dist_list

思路：广度优先搜索，在搜索过程中同时储存点位到0的最近距离。此题可以理解为多元广度优先搜索，存在多个零。按照之前的广度优先搜索，则是一个散发点来寻求最优距离，而多个零，不容易判断。因此我们可以采取一种新思路：超级零，超级零和所有的0都链接在一起，且距离为0。超级零在矩阵之外，求超级零到各个1的距离。因此超级零的下一层则是矩阵中的各个零点，之后零点再向外扩散寻找1，从而确定最短距离。

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        # 初始化动态规划的数组，所有的距离值都设置为一个很大的数
        dist = [[10**9] * n for _ in range(m)]
        # 如果 (i, j) 的元素为 0，那么距离为 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    dist[i][j] = 0
        # 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
        for i in range(m):
            for j in range(n):
                if i - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
                if j - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)
        # 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i + 1 < m:
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
                if j + 1 < n:
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)
        return dist

思路：通过两次遍历（一次为左上（比较一个点的左边和上边），一次为右下（比较一个点的右边和下边））通过动态规划来储存当前点到最近的0的距离。具体思路可看官网思路。

GO

func updateMatrix(mat [][]int) [][]int {
    xy := [][]int{{-1, 0}, {0, 1}, {0, -1}, {1, 0}}
    mat_r, mat_c := len(mat), len(mat[0])
    dist := [][]int{}
    que := [][]int{}
    for i := 0; i < mat_r; i++ {
        dist_r := []int{}
        for j := 0; j < mat_c; j++ {
            if mat[i][j] == 0 {
                que = append(que, []int{i, j})
                dist_r = append(dist_r, 0)
            } else {
                dist_r = append(dist_r, -1)
            }
        }
        dist = append(dist, dist_r)
    }
    for len(que)> 0 {
        r1, c1 := que[0][0], que[0][1]
        que = que[1:]
        for i := 0; i < len(xy); i++ {
            r2, c2 := r1+xy[i][0], c1+xy[i][1]
            if 0 <= r2 && r2 < mat_r && 0 <= c2 && c2 < mat_c && dist[r2][c2] == -1 {
                dist[r2][c2] =dist[r1][c1]+1
                que = append(que, []int{r2, c2})
            }
        }
    }
    return dist
}

思路：参考第一篇python代码。

func updateMatrix(mat [][]int) [][]int {
    mat_r,mat_c:=len(mat),len(mat[0])
    dict:=[][]int{}
    for i:=0;i<mat_r;i++{
        dict_r:=[]int{}
        for j:=0;j<mat_c;j++{
            if mat[i][j]==0{
                dict_r=append(dict_r,0)
            }else{
                dict_r=append(dict_r,10000)
            }
        }
        dict=append(dict,dict_r)
    }
    for i:=0;i<mat_r;i++{
        for j:=0;j<mat_c;j++{
            if i>=1{
                dict[i][j] = min(dict[i][j], dict[i - 1][j] + 1)
            }
            if j>=1{
                dict[i][j] = min(dict[i][j], dict[i][j-1] + 1)
            }
        }
    }
    for i:=mat_r-1;i>=0;i--{
        for j:=mat_c-1;j>=0;j--{
            if i<mat_r-1{
                dict[i][j] = min(dict[i][j], dict[i+1][j] + 1)
            }
            if j<mat_c-1{
                dict[i][j] = min(dict[i][j], dict[i][j+1] + 1)
            }
        }
    }
    return dict
}
func min(x,y int) int{
    if x>y{
        return y
    }
    return x
}

思路：参考第二篇python代码

994. 腐烂的橘子

在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
具体题目链接

Python

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        grid_r,grid_c,minute,good=len(grid),len(grid[0]),0,0
        bad=[(i,j) for j in range(grid_c) for i in range(grid_r) if grid[i][j]==2]
        for i in grid:#统计好橘子个数
            for j in i:
                if j==1:
                    good+=1
        if good==0:#好橘子个数为0直接返回
            return 0
        que=collections.deque(bad)#将坏橘子加到队列中
        while que:
            lenq=len(que)
            for i in range(lenq):#保证一次性执行一圈橘子
                r1,c1=que.popleft()
                for r2,c2 in [(r1-1,c1),(r1,c1+1),(r1,c1-1),(r1+1,c1)]:
                    if 0<=r2<grid_r and 0<=c2<grid_c and grid[r2][c2] and grid[r2][c2]==1:
                        que.append((r2,c2))
                        grid[r2][c2]=2
                        good-=1
            minute+=1
            if good==0:#好橘子个数为0则返回。
                return minute
        return -1#若队列执行完毕还没有返回，则证明存在无法感染的橘子，因此返回-1

思路：此题一看到就想起广域优先搜索并逐层搜索。通过good的个数来判断是否完成感染。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        grid_r,grid_c,minute=len(grid),len(grid[0]),0
        bad=[(i,j,minute) for j in range(grid_c) for i in range(grid_r) if grid[i][j]==2]
        que=collections.deque(bad)
        while que:
            r1,c1,minute=que.popleft()
            for r2,c2 in [(r1-1,c1),(r1,c1+1),(r1,c1-1),(r1+1,c1)]:
                if 0<=r2<grid_r and 0<=c2<grid_c and grid[r2][c2] == 1:
                    que.append((r2,c2,minute+1))
                    grid[r2][c2]=2
        for row in grid:
            if 1 in row: return -1
        return minute

思路：此思路与上述代码相同，但是简化一些，将时间minute添加到每一次队列中，同步更新。

GO

func orangesRotting(grid [][]int) int {
    grid_r,grid_c,minute:=len(grid),len(grid[0]),0
    que:=[][]int{}
    direction:=[][]int{{-1,0},{0,1},{0,-1},{1,0}}
    for i:=0;i<grid_r;i++{
        for j:=0;j<grid_c;j++{
            if grid[i][j]==2{
                que=append(que,[]int{i,j,minute})
                }
            }
            
    }
    for len(que)>0{
        r1,c1:=que[0][0],que[0][1]
        minute=que[0][2]
        que=que[1:]
        for i:=0;i<4;i++{
            r2,c2:=r1+direction[i][0],c1+direction[i][1]
            if 0<=r2 && r2<grid_r && 0<=c2&&c2<grid_c && grid[r2][c2]==1{
                que=append(que,[]int{r2,c2,minute+1})
                grid[r2][c2]=2
            }
        }
    }
    for i:=0;i<grid_r;i++{
        for j:=0;j<grid_c;j++{
            if grid[i][j]==1{
                return -1
            }
        }
    }
    return minute
}

思路:同python思路