542. 01 Matrix - Medium

前往題目

想法

• 為了這題先花了兩三個小時弄懂直到能自己寫出BFS
• 隔一天再來挑戰這題寫的就蠻順的，但是回想BFS加上coding，從頭寫到尾就花了半小時
• 最後雖然還是fail，但離正解只差一步之遙
• 原因是沒完全搞清楚需要更新的cell以及不用更新的cell之間的關係
• 因為需要更新的cell，初始值是1，讓我腦袋打結

思路

由於是算距離，所以這題利用BFS不斷更新每個相鄰cell的距離

1. 一樣先記錄幾行幾列，上下左右方向定義好 (這些都是BFS模板有的)
2. 接著紀錄終點，也就是0都在哪些位置，放到queue裡面，其餘用-1填充
3. 然後從每個終點開始的上下左右cell開始更新
4. 被更新的cell一樣放到queue以待下次成為新的終點，看其上下左右cell更新數值

Code

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        final int M = mat.length; // Row size of mat
        final int N = mat[0].length; // Column size of mat
        
        final int ZERO = 0;
        final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // Directions of up, down, left, right

        // Queue for the '0's positions
        Queue<int[]> q = new LinkedList<>();

        // Dummy value indicating the cell that haven't been calculated
        final int DUMMY_VALUE = -1;

        // Record the address that needed to be updated
        for(int row = 0; row < M; ++row){
            for(int col = 0; col < N; ++col){
                // Record all the '0' position
                if(mat[row][col] == ZERO){
                    q.add(new int[]{row, col});
                } else{
                    mat[row][col] = DUMMY_VALUE; // Fill the cell with dummy value
                }
            }
        }

        // BFS to update the distance
        while(!q.isEmpty()){
            int[] curPos = q.poll(); // Current position
            int rowCurPos = curPos[0]; // Row of the current position
            int colCurPos = curPos[1]; // Column of the current position
            
            // Check all the directions of the ZERO
            for(int[] direction : DIRECTIONS){
                int rowSurr = rowCurPos + direction[0]; // Row of the surrounding cell
                int colSurr = colCurPos + direction[1]; // Column of the surrounding cell

                // Check in boundary and it's not the '1' which close to '0'
                if(isBound(M, N, rowSurr, colSurr) && mat[rowSurr][colSurr] == DUMMY_VALUE){
                    q.add(new int[]{rowSurr, colSurr});
                    mat[rowSurr][colSurr] = mat[rowCurPos][colCurPos] + 1;
                }

            }
        }

        return mat;
    }

    // Check if the position is in the boundary of the matrix
    private boolean isBound(int matM, int matN, int row, int col){
        return row >= 0 && row < matM && col >= 0 && col < matN; 
    }
}

2023/12/08

再次嘗試，但有點掙扎，沒想到是除了0以外的全部都賦值為-1

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        final int M = mat.length;
        final int N = mat[0].length;

        final int[][] DIRS = {{0, 1},{0, -1},{1, 0},{-1, 0}};

        // Dummy value indicating the cell that haven't been calculated
        final int DUMMY_VAL = -1;

        Queue<int[]> q = new LinkedList<>();

        for (int m = 0; m < M; ++m) {
            for (int n = 0; n < N; ++n) {
                if (mat[m][n] == 0) {
                    q.add(new int[]{m, n});
                } else {
                    mat[m][n] = DUMMY_VAL;
                }
            }
        }

        while(!q.isEmpty()) {
            int[] cell = q.poll();

            // Check four directions
            for (int[] dir : DIRS) {
                int row = dir[0] + cell[0];
                int col = dir[1] + cell[1];

                if (inBound(M, N, row, col) && mat[row][col] == DUMMY_VAL) {
                    q.add(new int[]{row, col});
                    mat[row][col] = mat[cell[0]][cell[1]] + 1;
                }
            }
        }

        return mat;
    }

    private boolean inBound(int m, int n, int row, int col) {
        return row >= 0 && row < m && col >= 0 && col < n;
    }
}