542. 01 Matrix #

Problem #

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Problem Summary #

Given a matrix consisting of 0s and 1s, find the distance from each element to the nearest 0. The distance between two adjacent elements is 1.

Solution Ideas #

Given a two-dimensional array containing only 0s and 1s, calculate the distance from each 1 to the nearest 0.
There are 3 solutions to this problem. The first solution is the easiest to think of: BFS. First preprocess the board by changing every 0 to -1 and every 1 to 0. Enqueue every -1 (that is, the 0s in the original board). Each time a node is dequeued, enqueue its 4 surrounding positions. This is like throwing a stone into a lake: ripples spread out circle by circle, and each circle is one level. Since we initialized the board, all -1s are positions that were originally 0, so when the ripple reaches these -1 points, they do not need to be processed. The points on the board that are 0 are positions that were originally 1; when the ripple reaches these points, their level needs to be assigned and updated. When a later ripple reaches a point that was originally 1 again, since its value has already been updated by the first ripple that reached it, it does not need to be updated again. (The first ripple to arrive must be the shortest.)
The second solution is DFS. First preprocess by resetting all 1s that have no surrounding 0s to the maximum value. For 1s that have a surrounding 0, their distance to a 0 is 1, so these points do not need to be changed. The points that actually need to be updated are precisely those with no surrounding 0s. When the recursive step count val is smaller than the value of the point (which is why we first update 1s to the maximum value), keep updating it.
The third solution is DP. Since there are 4 directions, processing 2 directions at a time can reduce the time complexity. The first pass traverses from top to bottom and from left to right, first handling the top and left directions. The second pass traverses from bottom to top and from right to left, then handling the right and bottom directions.

Code #


package leetcode

import (
	"math"
)

// Solution 1: BFS
func updateMatrixBFS(matrix [][]int) [][]int {
	res := make([][]int, len(matrix))
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return res
	}
	queue := make([][]int, 0)
	for i := range matrix {
		res[i] = make([]int, len(matrix[0]))
		for j := range res[i] {
			if matrix[i][j] == 0 {
				res[i][j] = -1
				queue = append(queue, []int{i, j})
			}
		}
	}
	level := 1
	for len(queue) > 0 {
		size := len(queue)
		for size > 0 {
			size--
			node := queue[0]
			queue = queue[1:]
			i, j := node[0], node[1]
			for _, direction := range [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}} {
				x := i + direction[0]
				y := j + direction[1]
				if x < 0 || x >= len(matrix) || y < 0 || y >= len(matrix[0]) || res[x][y] < 0 || res[x][y] > 0 {
					continue
				}
				res[x][y] = level
				queue = append(queue, []int{x, y})
			}
		}
		level++
	}
	for i, row := range res {
		for j, cell := range row {
			if cell == -1 {
				res[i][j] = 0
			}
		}
	}
	return res
}

// Solution 2: DFS
func updateMatrixDFS(matrix [][]int) [][]int {
	result := [][]int{}
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return result
	}
	maxRow, maxCol := len(matrix), len(matrix[0])
	for r := 0; r < maxRow; r++ {
		for c := 0; c < maxCol; c++ {
			if matrix[r][c] == 1 && hasZero(matrix, r, c) == false {
				// Specially handle 1s with no surrounding 0s by setting them to the maximum value
				matrix[r][c] = math.MaxInt64
			}
		}
	}
	for r := 0; r < maxRow; r++ {
		for c := 0; c < maxCol; c++ {
			if matrix[r][c] == 1 {
				dfsMatrix(matrix, r, c, -1)
			}
		}
	}
	return (matrix)
}

// Determine whether there is a 0 around it
func hasZero(matrix [][]int, row, col int) bool {
	if row > 0 && matrix[row-1][col] == 0 {
		return true
	}
	if col > 0 && matrix[row][col-1] == 0 {
		return true
	}
	if row < len(matrix)-1 && matrix[row+1][col] == 0 {
		return true
	}
	if col < len(matrix[0])-1 && matrix[row][col+1] == 0 {
		return true
	}
	return false
}

func dfsMatrix(matrix [][]int, row, col, val int) {
	// Do not exceed the board bounds, and val must be smaller than matrix[row][col]
	if row < 0 || row >= len(matrix) || col < 0 || col >= len(matrix[0]) || (matrix[row][col] <= val) {
		return
	}
	if val > 0 {
		matrix[row][col] = val
	}
	dfsMatrix(matrix, row-1, col, matrix[row][col]+1)
	dfsMatrix(matrix, row, col-1, matrix[row][col]+1)
	dfsMatrix(matrix, row+1, col, matrix[row][col]+1)
	dfsMatrix(matrix, row, col+1, matrix[row][col]+1)
}

// Solution 3: DP
func updateMatrixDP(matrix [][]int) [][]int {
	for i, row := range matrix {
		for j, val := range row {
			if val == 0 {
				continue
			}
			left, top := math.MaxInt16, math.MaxInt16
			if i > 0 {
				top = matrix[i-1][j] + 1
			}
			if j > 0 {
				left = matrix[i][j-1] + 1
			}
			matrix[i][j] = min(top, left)
		}
	}
	for i := len(matrix) - 1; i >= 0; i-- {
		for j := len(matrix[0]) - 1; j >= 0; j-- {
			if matrix[i][j] == 0 {
				continue
			}
			right, bottom := math.MaxInt16, math.MaxInt16
			if i < len(matrix)-1 {
				bottom = matrix[i+1][j] + 1
			}
			if j < len(matrix[0])-1 {
				right = matrix[i][j+1] + 1
			}
			matrix[i][j] = min(matrix[i][j], min(bottom, right))
		}
	}
	return matrix
}