Сложность: medium
Вам дана сетка размером 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]]
👨💻 Алгоритм:
1⃣Обход всех комнат:
Пройдите через каждую клетку сетки, инициализируя очередь для BFS. Если клетка содержит ворота (0), добавьте её в очередь.
2⃣BFS для поиска кратчайшего пути:
Используйте BFS для распространения из каждого ворот в соседние пустые комнаты. Обновите значение расстояния до ближайших ворот для каждой комнаты, которую вы посещаете, если это расстояние меньше текущего значения.
3⃣Проверка всех направлений:
Для каждой клетки проверьте все возможные направления (вверх, вниз, влево, вправо) и добавляйте в очередь те, которые являются пустыми комнатами.
😎 Решение:
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));
}
}
}
}
}
Ставь 👍 и забирай 📚 Базу знаний