542. 01 Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 104

• 1 <= m * n <= 104

• mat[i][j] is either 0 or 1.

• There is at least one 0 in mat.

My Solutions:

和64题类似

public int[][] updateMatrix(int[][] mat) {
    int rows = mat.length, cols = mat[0].length;
    int max = rows + cols - 2; // 如果只有一个1在角落，这是最大可能的长度
    int first, second; // 可能的选择，从上下或者左右过来。也可以另外建一个数组储存结果
	
    // 第一遍检查从上一层或者左边一列过来
    for (int i = 0; i < rows; i++) {
	for (int j = 0; j < cols; j++) {
	    if (mat[i][j] == 0) continue; // 如果有另外的数组可以储存，dist[i][j] = 0;
	    first = max;
            second = max;
	    if (i > 0) first = mat[i - 1][j]; // 从上一层过来。如果有另外的数组可以储存， dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
	    if (j > 0) second = mat[i][j - 1]; // 从左边一列过来。如果有另外的数组可以储存，dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
	    mat[i][j] = Math.min(first, second) + 1;
	}
    }
	
    // 第二遍检查从下层或者右边一列过来
    for (int i = rows - 1; i >= 0; i--) {
	for (int j = cols - 1; j >= 0; j--) {
	    if (mat[i][j] == 0) continue;
		first = max;
	        second = max;
		if (i < rows - 1) first = mat[i + 1][j]; // 从下一层过来，也可以 dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
		if (j < cols - 1) second = mat[i][j + 1]; // 从右边一列过来，也可以 dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
		mat[i][j] = Math.min(Math.min(first, second) + 1, mat[i][j]); // 如果有另外的数组，不需要这一步
	}
    }
    return mat;
}

还有一种从0点周边出发，一层一层增加的解法。

• For convinience, let's call the cell with value 0 as zero-cell, the cell has with value 1 as one-cell, the distance of the nearest 0 of a cell as distance.

• Firstly, we can see that the distance of all zero-cells are 0.

• Same idea with Topology Sort, we process zero-cells first, then we use queue data structure to keep the order of processing cells, so that cells which have the smaller distance will be processed first. - Then we expand the unprocessed neighbors of the current processing cell and push into our queue.

• Afterall, we can achieve the minimum distance of all cells in our matrix.

int[] DIR = new int[]{0, 1, 0, -1, 0};

public int[][] updateMatrix(int[][] mat) {
    
    int rows = mat.length, cols = mat[0].length;
    Queue<int[]> q = new LinkedList<>();
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (mat[i][j] == 0) q.offer(new int[]{i,j});
            else mat[i][j] = -1; // marked as not processed 
        }
    }
    
    while (!q.isEmpty()) {
        int[] curr = q.poll();
        int r = curr[0], c = curr[1];
        
        for (int i = 0; i < 4; i++) {
            //(0, 1), (1, 0), (0, -1), (-1, 0)
            int nextR = r + DIR[i], nextC = c + DIR[i + 1]; 
            if (nextR < 0 || nextR == rows 
                || nextC < 0 || nextC == cols 
                    || mat[nextR][nextC] == -1) continue;
            mat[nextR][nextC]= mat[r][c] + 1;
            q.offer(new int[]{nextR, nextC});
        }
    }
    return mat;
}