Сложность: hard
Дана сетка m x n, содержащая значения 0, 1 или 2, где:
каждое 0 обозначает пустую землю, по которой можно свободно проходить,
каждое 1 обозначает здание, через которое нельзя пройти,
каждое 2 обозначает препятствие, через которое нельзя пройти.
Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо.
Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1.
Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи.
Пример:
Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
👨💻 Алгоритм:
1⃣Инициализация и запуск BFS
Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки.
2⃣Обработка BFS и обновление расстояний
При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX.
3⃣Обновление и возврат минимального расстояния
Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1.
😎 Решение:
class Solution {
bfs(grid, row, col, totalHouses) {
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const rows = grid.length, cols = grid[0].length;
let distanceSum = 0, housesReached = 0, steps = 0;
const q = [[row, col]];
const vis = Array.from({ length: rows }, () => Array(cols).fill(false));
vis[row][col] = true;
while (q.length && housesReached !== totalHouses) {
let size = q.length;
while (size-- > 0) {
const [r, c] = q.shift();
if (grid[r][c] === 1) {
distanceSum += steps;
housesReached++;
continue;
}
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] !== 2) {
vis[nr][nc] = true;
q.push([nr, nc]);
}
}
}
steps++;
}
if (housesReached !== totalHouses) {
for (let r = 0; r < rows;Ставь 👍 и забирай 📚 Базу знаний