286. Walls and Gates
Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями:
-1: Стена или препятствие.
0: Ворота.
INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 =
2147483647
для представления INF, так как можно предположить, что расстояние до ворот меньше
2147483647
.
Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF.
示例:
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
C# 解法
匹配/原始using System;
using System.Collections.Generic;
public class Solution {
private static readonly int INF = 2147483647;
private static readonly int[][] Directions = new int[][] {
new int[] { 0, 1 },
new int[] { 1, 0 },
new int[] { 0, -1 },
new int[] { -1, 0 }
};
public void WallsAndGates(int[][] rooms) {
if (rooms.Length == 0) return;
int m = rooms.Length;
int n = rooms[0].Length;
Queue<(int, int)> queue = new Queue<(int, int)>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 0) {
queue.Enqueue((i, j));
}
}
}
while (queue.Count > 0) {
var (x, y) = queue.Dequeue();
foreach (var direction in Directions) {
int nx = x + direction[0];
int ny = y + direction[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
rooms[nx][ny] = rooms[x][y] + 1;
queue.Enqueue((nx, ny));
}
}
}
}
}C++ 解法
自动草稿，提交前请检查#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 static readonly int INF = 2147483647;
private static readonly int[][] Directions = new int[][] {
new int[] { 0, 1 },
new int[] { 1, 0 },
new int[] { 0, -1 },
new int[] { -1, 0 }
};
public void WallsAndGates(int[][] rooms) {
if (rooms.size() == 0) return;
int m = rooms.size();
int n = rooms[0].size();
queue<(int, int)> queue = new queue<(int, int)>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 0) {
queue.Enqueue((i, j));
}
}
}
while (queue.size() > 0) {
var (x, y) = queue.Dequeue();
foreach (var direction in Directions) {
int nx = x + direction[0];
int ny = y + direction[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
rooms[nx][ny] = rooms[x][y] + 1;
queue.Enqueue((nx, ny));
}
}
}
}
}Java 解法
匹配/原始import java.util.LinkedList;
import java.util.Queue;
public class Solution {
private static final int INF = 2147483647;
private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public void wallsAndGates(int[][] rooms) {
int m = rooms.length;
if (m == 0) return;
int n = rooms[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 0) {
queue.add(new int[]{i, j});
}
}
}
while (!queue.isEmpty()) {
int[] point = queue.poll();
int x = point[0], y = point[1];
for (int[] direction : directions) {
int nx = x + direction[0];
int ny = y + direction[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
rooms[nx][ny] = rooms[x][y] + 1;
queue.add(new int[]{nx, ny});
}
}
}
}
}JavaScript 解法
匹配/原始var wallsAndGates = function(rooms) {
if (rooms.length === 0) return;
const m = rooms.length;
const n = rooms[0].length;
const queue = [];
const INF = 2147483647;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (rooms[i][j] === 0) {
queue.push([i, j]);
}
}
}
while (queue.length > 0) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] === INF) {
rooms[nx][ny] = rooms[x][y] + 1;
queue.push([nx, ny]);
}
}
}
};Python 解法
匹配/原始from collections import deque
class Solution:
def wallsAndGates(self, rooms):
if not rooms:
return
m, n = len(rooms), len(rooms[0])
queue = deque()
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
queue.append((i, j))
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and rooms[nx][ny] == 2147483647:
rooms[nx][ny] = rooms[x][y] + 1
queue.append((nx, ny))Go 解法
匹配/原始package main
import "container/list"
func wallsAndGates(rooms [][]int) {
if len(rooms) == 0 {
return
}
m, n := len(rooms), len(rooms[0])
q := list.New()
INF := 2147483647
directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if rooms[i][j] == 0 {
q.PushBack([2]int{i, j})
}
}
}
for q.Len() > 0 {
front := q.Front()
q.Remove(front)
x, y := front.Value.([2]int)[0], front.Value.([2]int)[1]
for _, dir := range directions {
nx, ny := x+dir[0], y+dir[1]
if nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF {
rooms[nx][ny] = rooms[x][y] + 1
q.PushBack([2]int{nx, ny})
}
}
}
}Algorithm
Обход всех комнат:
Пройдите через каждую клетку сетки, инициализируя очередь для BFS. Если клетка содержит ворота (0), добавьте её в очередь.
BFS для поиска кратчайшего пути:
Используйте BFS для распространения из каждого ворот в соседние пустые комнаты. Обновите значение расстояния до ближайших ворот для каждой комнаты, которую вы посещаете, если это расстояние меньше текущего значения.
Проверка всех направлений:
Для каждой клетки проверьте все возможные направления (вверх, вниз, влево, вправо) и добавляйте в очередь те, которые являются пустыми комнатами.
😎
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.