#542. 01 Matrix

題目描述

給你一個m x n的二元陣列 mat，回傳每一格和0的最近距離。

每一格之間的距離是1。

限制條件

m == mat.length
n == mat[i].length
1 <= m, n <= 10⁴
1 <= m * n <= 10⁴
mat[i][j]只會是0或1。
陣列中最少會有一個格子是0。

這一題首先要先確認我們該做些什麼事情，主要目標是處理每一個格子並且找出它與最近的0的距離。分析一下，如果格子是1的話，我們並不知道它實際與最近的0的距離是多少，因此從1出發並不是個好的策略，但是換作是從0出發，它與最近的非0格子的距離一定是1，一直往下延伸，離距離1的格子最近的格子並且沒有檢查過的值一定會是2，以此類推，可以一步一步的延伸下去直到填滿所有的格子。

把完成主要目標的步驟細分一下，會有下面這幾件事情。

先檢查每一個格子。
如果格子是0，不做標記，但是把它存入起始的處理佇列。
如果格子是1，先標記成-1，表示尚未完成。
如果是0，將它上下左右不為0而且未完成的格子填入距離值。

BFS

public class Solution { 
	public int[][] UpdateMatrix(int[][] mat) {
        var q = new Queue<(int,int)>();        
        //pick cells in 0 value.
        //mark other cells to -1 as a not finished cell.
        for(int i=0;i<mat.Length;i++){
            for(int j=0;j<mat[i].Length;j++){
                if(mat[i][j]==0) q.Enqueue((i,j));
                else mat[i][j] = -1;
            }
        }
        //process the cell.
        while(q.Count!=0){
            (int row,int col) = q.Dequeue();
            if(isValid(mat,row+1,col)) {mat[row+1][col] = mat[row][col]+1; q.Enqueue((row+1,col));}
            if(isValid(mat,row-1,col)) {mat[row-1][col] = mat[row][col]+1; q.Enqueue((row-1,col));}
            if(isValid(mat,row,col+1)) {mat[row][col+1] = mat[row][col]+1; q.Enqueue((row,col+1));}
            if(isValid(mat,row,col-1)) {mat[row][col-1] = mat[row][col]+1; q.Enqueue((row,col-1));}            
        }
        return mat;
    }
    public bool isValid(int[][] mat, int i, int j){
        if(i>=0 && i<mat.Length && j>=0 && j<mat[0].Length && mat[i][j]==-1 ) return true;
        return false;
    }
}

複雜度分析：

時間複雜度：起初會先尋找0值得格子，需要花上m * n的時間，再來處理所有格子也會花上m * n的時間，總時間為 2 * m *n，因此時間複雜度為O(m * n);
空間複雜度：空間複雜度為O(m*n)；

#542. 01 Matrix

題目描述

限制條件

解題思路

BFS

學習重點