Задача: 317. Shortest Distance from All Buildings
Сложность: 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.

😎 Решение:

import java.util.*;

class Solution {
    private int bfs(int[][] grid, int row, int col, int totalHouses) {
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int rows = grid.length, cols = grid[0].length;
        int distanceSum = 0, housesReached = 0, steps = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{row, col});
        boolean[][] vis = new boolean[rows][cols];
        vis[row][col] = true;

        while (!q.isEmpty() && housesReached != totalHouses) {
            int size = q.size();
            while (size-- > 0) {
                int[] curr = q.poll();
                int r = curr[0], c = curr[1];
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                for (int[] dir : dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] != 2) {
                        vis[nr][nc] = true;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 0 && vis[r][c]) grid[r][c] = 2;
                }
            }
            return Integer.MAX_VALUE;
        }
        return distanceSum;
    }

    public int shortestDistance(int[][] grid) {
        int minDistance = Integer.MAX_VALUE, rows = grid.length, cols = grid[0].length, totalHouses = 0;
        for (int[] row : grid) for (int cell : row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = Math.min(minDistance, bfs(grid, r, c, totalHouses));
        return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
    }
}

Ставь 👍 и забирай 📚 Базу знаний