Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки.
Расстояние между двумя соседними ячейками равно 1.
Пример:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
C# решение
сопоставлено/оригиналusing System.Collections.Generic;
public class Solution {
private int m;
private int n;
private int[][] directions = new int[][] {
new int[] {0, 1},
new int[] {1, 0},
new int[] {0, -1},
new int[] {-1, 0}
};
public int[][] UpdateMatrix(int[][] mat) {
m = mat.Length;
n = mat[0].Length;
int[][] matrix = new int[m][];
bool[][] seen = new bool[m][];
Queue<int[]> queue = new Queue<int[]>();
for (int i = 0; i < m; i++) {
matrix[i] = new int[n];
seen[i] = new bool[n];
for (int j = 0; j < n; j++) {
matrix[i][j] = mat[i][j];
if (matrix[i][j] == 0) {
queue.Enqueue(new int[] {i, j, 0});
seen[i][j] = true;
}
}
}
while (queue.Count > 0) {
int[] curr = queue.Dequeue();
int row = curr[0], col = curr[1], steps = curr[2];
foreach (var direction in directions) {
int nextRow = row + direction[0], nextCol = col + direction[1];
if (IsValid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
seen[nextRow][nextCol] = true;
queue.Enqueue(new int[] {nextRow, nextCol, steps + 1});
matrix[nextRow][nextCol] = steps + 1;
}
}
}
return matrix;
}
private bool IsValid(int row, int col) {
return 0 <= row && row < m && 0 <= col && col < n;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private int m;
private int n;
private int[][] directions = new int[][] {
new int[] {0, 1},
new int[] {1, 0},
new int[] {0, -1},
new int[] {-1, 0}
};
public int[][] UpdateMatrix(int[][] mat) {
m = mat.size();
n = mat[0].size();
int[][] matrix = new int[m][];
bool[][] seen = new bool[m][];
queue<int[]> queue = new queue<int[]>();
for (int i = 0; i < m; i++) {
matrix[i] = new int[n];
seen[i] = new bool[n];
for (int j = 0; j < n; j++) {
matrix[i][j] = mat[i][j];
if (matrix[i][j] == 0) {
queue.Enqueue(new int[] {i, j, 0});
seen[i][j] = true;
}
}
}
while (queue.size() > 0) {
vector<int>& curr = queue.Dequeue();
int row = curr[0], col = curr[1], steps = curr[2];
foreach (var direction in directions) {
int nextRow = row + direction[0], nextCol = col + direction[1];
if (IsValid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
seen[nextRow][nextCol] = true;
queue.Enqueue(new int[] {nextRow, nextCol, steps + 1});
matrix[nextRow][nextCol] = steps + 1;
}
}
}
return matrix;
}
private bool IsValid(int row, int col) {
return 0 <= row && row < m && 0 <= col && col < n;
}
}Java решение
сопоставлено/оригиналimport java.util.LinkedList;
import java.util.Queue;
class Solution {
int m;
int n;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int[][] updateMatrix(int[][] mat) {
m = mat.length;
n = mat[0].length;
int[][] matrix = new int[m][n];
boolean[][] seen = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
matrix[row][col] = mat[row][col];
if (matrix[row][col] == 0) {
queue.add(new int[]{row, col, 0});
seen[row][col] = true;
}
}
}
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int row = curr[0], col = curr[1], steps = curr[2];
for (int[] direction : directions) {
int nextRow = row + direction[0], nextCol = col + direction[1];
if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
seen[nextRow][nextCol] = true;
queue.add(new int[]{nextRow, nextCol, steps + 1});
matrix[nextRow][nextCol] = steps + 1;
}
}
}
return matrix;
}
private boolean valid(int row, int col) {
return 0 <= row && row < m && 0 <= col && col < n;
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
constructor() {
this.m = 0;
this.n = 0;
this.directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
}
updateMatrix(mat) {
this.m = mat.length;
this.n = mat[0].length;
let matrix = Array.from({ length: this.m }, () => Array(this.n).fill(0));
let seen = Array.from({ length: this.m }, () => Array(this.n).fill(false));
let queue = [];
for (let row = 0; row < this.m; row++) {
for (let col = 0; col < this.n; col++) {
matrix[row][col] = mat[row][col];
if (matrix[row][col] === 0) {
queue.push([row, col, 0]);
seen[row][col] = true;
}
}
}
while (queue.length) {
let [row, col, steps] = queue.shift();
for (let direction of this.directions) {
let nextRow = row + direction[0];
let nextCol = col + direction[1];
if (this.valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
seen[nextRow][nextCol] = true;
queue.push([nextRow, nextCol, steps + 1]);
matrix[nextRow][nextCol] = steps + 1;
}
}
}
return matrix;
}
valid(row, col) {
return 0 <= row && row < this.m && 0 <= col && col < this.n;
}
}Python решение
сопоставлено/оригиналfrom collections import deque
class Solution:
def __init__(self):
self.m = 0
self.n = 0
self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def updateMatrix(self, mat):
self.m = len(mat)
self.n = len(mat[0])
matrix = [[0] * self.n for _ in range(self.m)]
seen = [[False] * self.n for _ in range(self.m)]
queue = deque()
for row in range(self.m):
for col in range(self.n):
matrix[row][col] = mat[row][col]
if matrix[row][col] == 0:
queue.append((row, col, 0))
seen[row][col] = True
while queue:
row, col, steps = queue.popleft()
for dr, dc in self.directions:
nextRow, nextCol = row + dr, col + dc
if self.valid(nextRow, nextCol) and not seen[nextRow][nextCol]:
seen[nextRow][nextCol] = True
queue.append((nextRow, nextCol, steps + 1))
matrix[nextRow][nextCol] = steps + 1
return matrix
def valid(self, row, col):
return 0 <= row < self.m and 0 <= col < self.nGo решение
сопоставлено/оригиналpackage main
import (
"container/list"
)
type Solution struct {
m, n int
directions [4][2]int
}
func Constructor() Solution {
return Solution{
directions: [4][2]int{
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
},
}
}
func (s *Solution) updateMatrix(mat [][]int) [][]int {
s.m = len(mat)
s.n = len(mat[0])
matrix := make([][]int, s.m)
seen := make([][]bool, s.m)
queue := list.New()
for i := 0; i < s.m; i++ {
matrix[i] = make([]int, s.n)
seen[i] = make([]bool, s.n)
for j := 0; j < s.n; j++ {
matrix[i][j] = mat[i][j]
if matrix[i][j] == 0 {
queue.PushBack([3]int{i, j, 0})
seen[i][j] = true
}
}
}
for queue.Len() > 0 {
curr := queue.Remove(queue.Front()).([3]int)
row, col, steps := curr[0], curr[1], curr[2]
for _, direction := range s.directions {
nextRow, nextCol := row+direction[0], col+direction[1]
if s.isValid(nextRow, nextCol) && !seen[nextRow][nextCol] {
seen[nextRow][nextCol] = true
queue.PushBack([3]int{nextRow, nextCol, steps + 1})
matrix[nextRow][nextCol] = steps + 1
}
}
}
return matrix
}
func (s *Solution) isValid(row, col int) bool {
return 0 <= row && row < s.m && 0 <= col && col < s.n
}Algorithm
Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen.
Выполните BFS:
Пока очередь не пуста, извлекайте текущие row, col, steps из очереди.
Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen.
Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.