Наикратчайшее расстояние до всех домов

Источник: https://leetcode.com/problems/shortest-distance-from-all-buildings/

Дана матрица размером m x n называется grid заполнена значениями 0, 1 или 2, где:

• каждый 0 означает пустое пространство, на которое можно вступить;
  
• каждая 1 означает здание, на эту ячейку нельзя вступить;
  
• каждая 2 означает препятствие, на эту ячейку нельзя вступить.
  

Мы хотим построить дом на пустом пространстве так, чтобы расстояние от него до остальных домов было наикратчайшим. Разрешения направления движения по матрице: вверх, вниз, вправо, влево.

В ответе указать наикратчайшее рсстояние для такого дома. Если невозможно построить дом, чтобы остальные дома были для него доступны, вернуть -1.

Дистанция считается, как Manhattan Distance, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Пример 1:

Дано: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Результат: 7
Пояснение: Три здания находятся в чейках (0,0), (0,4), (2,2), и препятсвие в ячейке (0,2).
Ячейка (1,2) пустая и она идеальна для строительства нового дома, поскольку общая сумма расстояний до существующих домов минимальна и равна 3+3+1=7.
В ответе возвращаем 7.

Пример 2:

Дано: grid = [[1,0]]
Результат: 1

Пример 3:

Дано: grid = [[1]]
Результат: -1

Ограничения:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] значение равно 0, 1, или 2.
• В исходной матрице существуеь хотя бы один дом.

Идея решения

Здесь мы применяем простой ПЕРЕБОР. Для каждой пустой ячейки считаем:

• суммарное расстояние до других домов, избегая препятвия;
• количество домов, которые в принципе достижимы из ячейки.

Затем мы пробегаем по всем суммарных расстояний и выбираем наименьшее, если из этой ячейки ВСЕ дома достижимы. 

Чтобы сократить количество операций, мы отталкиваемся не от исходных пустых ячеек, а от существущих домов. И для каждого дома в каждой пустой ячейке записываем расстояние от дома до этой ячейки, суммируя значение с уже записанным, если оно есть.

Если мы рассматриваем какой-то существущий дом, то как мы считаем расстояние из него до пусиых ячеек? Используем ОЧЕРЕДЬ. То есть рассматриваем соседние с домом ячейки. И если они пустые и ни разу не посещенные из этого дома, то ставим их в очередь, а расстояние для них равно 1 и суммируется с подсчетами из других домов.. И для них повторяем ту же операцию с рассмотрением соседей, но расстояние будет уже 2, пока не рассмотрим все пустые ячейки.

То есть вокруг существующего дома мы строим "луковицу" со слоями достижимых соседей.

Имплементация

class Solution {
    public int shortestDistance(int[][] grid) {
    // проверка вырожденного случая
        if (grid.length == 0 || grid[0].length == 0) {
            return -1;
        }

        int m = grid.length;
        int n = grid[0].length;

// для каждой ячейки с 0 (пустая) собираем:
         int[][] distance = new int[m][n];  // суммарную дистанцию до 1 (дома)
        int[][] reachCount = new int[m][n]; // количество достигаемых домов (1)

// посчитаем сколько вообще домов у нас имеется
        int houseCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    houseCount++;
                }
            }
        }

// проверим каждый дом,
// достигается ли он из остальных домов
// и заодно посчитаем дистанции
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    //houseCount++;
                    if (!bfs(grid, distance, reachCount, houseCount, m, n, i, j)) {
                        return -1; // не достигаются все дома
                    }
                }
            }
        }

// решение существует, если мы не вышли до сих пор
        int minDistance = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
// ячейка пустая и из нее достигаются все дома,
// это потенциальный кандидат на строительство
                if (grid[i][j] == 0 && reachCount[i][j] == houseCount) {
                    minDistance = Math.min(minDistance, distance[i][j]);
                }
            }
        }
        return minDistance == Integer.MAX_VALUE ? -1 : minDistance;

    }

// вспомогательная функция
    private boolean bfs(int[][] grid, int[][] distance, int[][] reachCount, int houseCount, int m, int n, int x, int y) {

        int[][] visited = new int[m][n];
        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[]{x, y});  
        int[] dx = new int[]{0, 0, -1, 1};
        int[] dy = new int[]{1, -1, 0, 0};
        int level = 0;
        int count = 0;
// каждый новый уровень очереди - это как луковая шелуха вокруг ячейки
        while (!q.isEmpty()) {
            int size = q.size();
            level++;               
            for (int i = 0; i < size; i++) {//текущий уровень
                int[] curr = q.poll();
                for (int k = 0; k < 4; k++) { //все соседи ячейки
                    int nx = curr[0] + dx[k];
                    int ny = curr[1] + dy[k];
                    if (nx >=0 && ny >= 0 && nx < m && ny < n  && visited[nx][ny] == 0) {
                        if (grid[nx][ny] == 0) { // пустая
                            distance[nx][ny] += level;
                            visited[nx][ny] = 1;
                            reachCount[nx][ny]++;
                            q.offer(new int[]{nx, ny});
                        } else if (grid[nx][ny] == 1) { // дом
                            count++;
                            visited[nx][ny] = 1;
                        }
                    }
                }
            }
        }
        return count == houseCount;
    }
}