Сложность: 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⃣Проверка всех направлений:
Для каждой клетки проверьте все возможные направления (вверх, вниз, влево, вправо) и добавляйте в очередь те, которые являются пустыми комнатами.
😎 Решение:
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]);
}
}
}
};Ставь 👍 и забирай 📚 Базу знаний