Leetcode - 01-matrix

https://leetcode.com/problems/01-matrix/

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]]

When finding a number which is not 0, use BFS to search latest 0. Use queue for that. Simple and easy.

func updateMatrix(matrix [][]int) [][]int {
	if len(matrix) == 0 {
		return matrix
	}
	result := make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		result[i] = make([]int, len(matrix[0]))
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				result[i][j] = 0
				continue
			}
			result[i][j] = step(matrix, i, j)
		}
	}

	return result
}

type position struct {
	x int
	y int
}

func step(matrix [][]int, i, j int) int {
	dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	queue := []position{{i, j}}
	steps := 0
	for len(queue) != 0 {
		size := len(queue)
		for m := 0; m < size; m++ {
			p := queue[m]
			x := p.x
			y := p.y
			if matrix[x][y] == 0 {
				return steps
			}
			for _, d := range dirs {
				newX := x + d[0]
				newY := y + d[1]
				if newX >= 0 && newY >= 0 && newX < len(matrix) && newY < len(matrix[0]) {
					queue = append(queue, position{newX, newY})
				}
			}
		}
		queue = queue[size:]
		steps++
	}

	return steps
}

# @param {Integer[][]} matrix
# @return {Integer[][]}
def update_matrix(matrix)
    r = matrix.length
    c = matrix[0].length
    result = Array.new(r){Array.new(c, 0)}
    for i in 0..matrix.length-1
        for j in 0..matrix[0].length-1
            if matrix[i][j] == 0
                result[i][j] = 0
                next
            end
            result[i][j] = get_distance(matrix, i, j)
        end
    end
    return result
end

def get_distance(matrix, i, j)
    dirs = [[-1,0],[1,0],[0,-1],[0,1]]
    queue = [[i, j]]
    count = 0
    while queue.length != 0
        size = queue.length
        for i in 0..size-1
            point = queue[i]
            x = point[0]
            y = point[1]
            if matrix[x][y] == 0
                return count
            end
            dirs.each do |d|
                new_x = x + d[0]
                new_y = y + d[1]
                if new_x >= 0 && new_y >= 0 && new_x < matrix.length && new_y < matrix[0].length
                    queue << [new_x, new_y]
                end
            end
        end
        queue = queue[size..-1]
        count += 1
    end
    return count
end

• 相关文章
• 全局相关文章