Shortest Distance from All Buildings

Question

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely. Each 1 marks a building which you cannot pass through. Each 2 marks an obstacle which you cannot pass through. For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

Solution

我想到的解法跟參考解答差不多，但我拿到 TLE。我的想法是，當 grid 值等於 1 的時候，去跑 bfs，然後照每棟 building 去新建一個 int[][] 存 bfs 結果。把這些 int[][] 都存在一個 list 裡，最後再根據 grid 值等於 0 時，去把這些表找出來並把該位置的各個 int[][] 值相加。

參考解答之後，其實不需要存在一個 list，只需要建立一個 int[][] distance，然後每次的結果根據上次的結果 += 起來就好。不過，這題麻煩就麻煩在，你是在 2D array 裡面做 BFS，會面臨到需要記錄該點有沒有在這次 iteration 被訪問過。可以用兩個方法來完成這件事：

1. 建立一個 boolean[][] 來記錄
2. 直接修改 grid 的值

解答用了第二種。絲路在於，我們有一個記錄目前總共有幾棟 building 的 num，先把 -num 傳進 bfs。由於一開始是 0，所以是 0 的點就可以在這次的 iteration 被訪問。被訪問到的點，在 grid 上面的值要減 1，用這個方式來記錄被訪問過。所以在下次 num = 1 時，傳進去會是 -1，那就可以只訪問上個 iteration 有被成功訪問到的點（題目要求最後的 house 必須建在每棟 building 都可以訪問到）

在 2D array 裡做 BFS，可以用 Queue〈int[]〉。網路上有些人選擇寫一個 Tuple class 來記錄

    final int[][] steps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int[][] distance;
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        distance = new int[grid.length][grid[0].length];
        int num = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    bfs(grid, i, j, -num);
                    num++;
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == -num) {
                    min = Math.min(distance[i][j], min);
                }
            }
        }

        return min == Integer.MAX_VALUE? -1 : min;
    }

    public void bfs(int[][] grid, int row, int col, int num) {
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{row, col});
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            for (int i = queue.size(); i > 0; i--) {
                int[] cur = queue.poll();
                for (int[] step : steps) {
                    int x = step[0] + cur[0], y = step[1] + cur[1];
                    if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == num) {
                        distance[x][y] += level;
                        queue.offer(new int[]{x, y});
                        grid[x][y]--;
                    }
                }
            }
        }
    }