# Leetcode - 01-matrix

violet posted @ Mar 01, 2020 08:17:15 AM in 算法 with tags Algorithm 算法 BFS ruby Golang , 391 阅读

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```
truecaller en ligne 说:
Jul 13, 2023 07:59:41 PM

Nous avons tous reçu un appel d’un numéro inconnu ou d’un appelant indésirable à un moment donné de notre vie. Et au fil du temps, le besoin de connaître l’identité de l’appelant se renforce. truecaller en ligne Le portail Truecaller fournit une recherche de numéro de téléphone en ligne sur sa plate-forme, et nous sommes là pour vous aider et c’est entièrement gratuit.

MBOSE 7th Class Syl 说:
Jul 19, 2023 09:29:05 PM

Students Should Download the Respective Stream wise MBOSE Board 7th Class Exam Syllabus Subjects of Hindi, English, Mathematics, Science, Social Science etc, Pdf Format Provide Check the same From our page here,Students need to Start Their Preparation by first Downloading the Stream wise MBOSE 7th Class Curriculum Syllabus 2024 Latest Edition.Meghalaya Board Class Syllabus 2024 is Designed in MBOSE 7th Class Syllabus 2024 Accordance with the NCERT Based Guidelines and helps Students to get an Overview of the Hindi, English Medium All Subject, MBOSE keeps a Class Exam Pattern with the aim to Provide a Quality Education for All Students, On the basis of the Current Educational Demands

(输入验证码)
or Ctrl+Enter