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