矩阵，BFS 最短距离探索

Walls and Gates

这题乍看之下特别像滑雪，于是想试试用 DFS + memoization，于是有了下面的代码，过了 25/62 个 test cases ，错在了一个

  • [0 , INF, 0, INF, INF]

  • [-1, -1 , 0 , -1 , INF]

  • [-1 , 0 , 0 , 0 , INF]

  • [-1 , INF , 0 , 0 , -1]

这样的 test case 上。

其原因是，当我们搜索 (0, 4) 这个位置时，dfs 搜索了相邻的 (0, 5)，这时候遇到了比较尴尬的境地:

  • 为了避免死循环，我们要把当前元素改一下，免得下一步的 dfs 重新探回来；

  • 但是在这个局部上，正解却偏偏要探回来，往左走才能碰到最近的 0.

  • 于是我们发现了这题和滑雪最大的不同：滑雪由于取值限制，是不用担心回头路的，但这题会。留回头路会死循环，不留回头路会算错。

于是下面的代码在如上的 test case 上会挂掉；

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        for(int i = 0; i < rooms.length; i++){
            for(int j = 0; j < rooms[0].length; j++){
                if(rooms[i][j] == Integer.MAX_VALUE) rooms[i][j] = memoizedSearch(rooms, i, j);
            }
        }
    }

    private int memoizedSearch(int[][] rooms, int x, int y){
        if(x < 0 || x >= rooms.length) return Integer.MAX_VALUE;
        if(y < 0 || y >= rooms[0].length) return Integer.MAX_VALUE;

        if(rooms[x][y] == 0) return 0;
        if(rooms[x][y] == -1) return Integer.MAX_VALUE;
        if(rooms[x][y] == Integer.MAX_VALUE){

            rooms[x][y] = -1;

            int N = memoizedSearch(rooms, x - 1, y);
            int S = memoizedSearch(rooms, x + 1, y);
            int W = memoizedSearch(rooms, x, y - 1);
            int E = memoizedSearch(rooms, x, y + 1);

            int min = Math.min(Math.min(N, S), Math.min(W, E));
            if(min == Integer.MAX_VALUE){
                rooms[x][y] = Integer.MAX_VALUE;
                return rooms[x][y];
            } else {
                rooms[x][y] = min + 1;
                return rooms[x][y];
            }

        } else {
            return rooms[x][y];
        }
    }
}

“和最短距离” 相关的问题，最靠谱的还是BFS 解法。

一个最容易想到的做法是，每个 INF 为起点，扫整个矩阵。每个起点走的最长距离是 O(mn)，总共有 O(mn) 个能的起点，所以复杂度为 O(m^2 * n^2)，太慢了。

改良版本是，我们不从 INF 的角度开始，而是反过来，从 0 开始往回找，沿路只添加看到的 INF; 由于是 BFS，从gate出发，第一次看到某个房间的时候就是最短距离。这样我们有 O(mn) 个可能的起点和位置要搜，然而每个位置只会进入队列一次，所以时间和空间复杂度都是 O(mn).

每个位置只看一次，并不一定要靠记忆化搜索，DFS / BFS flood filling 一样可以。事实上，大多数都是靠 flood filling，靠记忆化搜索的反而是少数。

另一个小技巧是，处理矩阵不一定非要拍成一维 index，队列里直接扔 int[] 也完全可以，还省事。

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if(rooms == null || rooms.length == 0) return;

        int rows = rooms.length;
        int cols = rooms[0].length;

        Queue<int[]> queue = new LinkedList<>();

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(rooms[i][j] == 0) queue.offer(new int[]{i, j}); 
            }
        }

        int distance = 1;

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int[] cur = queue.poll();

                int[] xDir = {0,0,-1,1};
                int[] yDir = {-1,1,0,0};

                for(int j = 0; j < 4; j++){
                    int[] next = {cur[0] + xDir[j], cur[1] + yDir[j]};

                    if(next[0] >= 0 && next[1] >= 0 && next[0] < rows && next[1] < cols){
                        if(rooms[next[0]][next[1]] == Integer.MAX_VALUE){
                            rooms[next[0]][next[1]] = distance;
                            queue.offer(next);
                        }
                    }
                }
            }
            distance ++;
        }
    }
}

Best Meeting Point

先说一下自己第一个不成功的尝试，那就是一维推导错了，以为是所有 X 坐标的平均值。

在一维情况下：

  • 只有一个点

    • 取当前点的位置；

  • 有两个点

    • 两点之间的任何位置都是等价的，等于区间大小；

  • 有三个点

    • 最外面两点之间的任意位置等价，距离和等于区间大小；

    • 于是剩下一个点，可以发现最优位置就是在点上；

  • 有 N 个点

    • 我们可以对于排序了的坐标从外向里配对消除，每一对的距离等于这对点形成的区间大小。

于是我我们可以总结为：

  • 点的个数为偶数，则最里面 pair 之间的任意位置等价；

  • 点的个数为奇数，则一定在最里面的中心点上；

  • 因此，最优点就是当前维度的中位数。

于是一个最直观的解法就是，记录所有的 "1" 的 X/Y 坐标，选中位数，再把所有的地方过一遍。

扫哪里是 1 + 用两次 quick select + 计算总的距离

O(mn) + O(m) + O(n) + O(m) + O(n) = O(mn)

不过从提交速度上看，这个解法速度不理想，而且写个 quick select 代码量就上去了，面试时候有点浪费时间。

public class Solution {
    public int minTotalDistance(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        List<Integer> listX = new ArrayList<>();
        List<Integer> listY = new ArrayList<>();

        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    listX.add(i);
                    listY.add(j);
                }
            }
        }

        int medianX = findMedian(listX, 0, listX.size() - 1);
        int medianY = findMedian(listY, 0, listY.size() - 1);
        int minDis = 0;

        for(int x : listX){
            minDis += Math.abs(medianX - x);
        }
        for(int y : listY){
            minDis += Math.abs(medianY - y);
        }

        return minDis;
    }

    private int findMedian(List<Integer> list, int start, int end){
        int pivot = list.get(start);
        int left = start;
        int right = end;

        while(left <= right){
            while(left <= right && list.get(left) <= pivot) left++;
            while(left <= right && list.get(right) >= pivot) right--;

            if(left < right) swap(list, left, right);
        }
        swap(list, start, right);

        int medianIndex = list.size() / 2;

        if(right == medianIndex){
            return list.get(right);
        } else if(right < medianIndex){
            return findMedian(list, right + 1, end);
        } else {
            return findMedian(list, start, right - 1);
        }
    }

    private void swap(List<Integer> list, int a, int b){
        int temp = list.get(a);
        list.set(a, list.get(b));
        list.set(b, temp);
    }
}

论坛上还有一个很有趣的解法，虽然时间复杂度不好看，但是思路巧妙，简洁易懂。

核心思想在于，最优 meeting point 一定是在所有点的中间，而对于每个 pair ，他们到 best meeting point 的距离和就是 pair 两点的区间长度，所以假设以 0 为远点，用双指针检查每一对就可以了。

public int minTotalDistance(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;

    List<Integer> I = new ArrayList<>(m);
    List<Integer> J = new ArrayList<>(n);

    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 1){
                I.add(i);
                J.add(j);
            }
        }
    }

    return getMin(I) + getMin(J);
}

private int getMin(List<Integer> list){
    int ret = 0;

    Collections.sort(list);

    int i = 0;
    int j = list.size() - 1;
    while(i < j){
        ret += list.get(j--) - list.get(i++);
    }

    return ret;
}

如果进一步利用循环的特点，甚至排序都可以省了，ArrayList 里自动就是排好序的。不过会扫两次 O(mn)，就有一个取舍的问题在里面了。

public class Solution {
    public int minTotalDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        List<Integer> I = new ArrayList<Integer>();
        List<Integer> J = new ArrayList<Integer>();

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    I.add(i);
                }
            }
        }
        for(int j = 0; j < n; j++) {
            for(int i = 0; i < m; i ++) {
                if(grid[i][j] == 1) {  
                    J.add(j);
                }
            }
        }
        return minTotalDistance(I) + minTotalDistance(J);
    }

    public int minTotalDistance(List<Integer> grid) {
        int i = 0, j = grid.size() - 1, sum = 0;

        while(i < j) {
            sum += grid.get(j--) - grid.get(i++);
        }
        return sum;
    }

}

Shortest Distance from All Buildings

乍看之下是上一题的强化版，因为所谓“距离”的定义是一样的，都是曼哈顿距离。最主要的不同点在于，中间有障碍之后，问题就不再是简单的分开维度拆分分析了，因为对于每一个位置，都要考虑障碍物的具体位置。

因此不难看出，这题变成了一个 Graph 问题，因为对于矩阵中任意两点 A & B，其最短距离只有靠 BFS 去查。 矩阵就是一种 uniform weight, undirected graph.

一个非常土的办法是，先扫一遍矩阵，找到 k 个起始点；对于每一个起始点开始做 BFS，记录到每一个其他格子的距离，每次扫完了要存这个位置到起点的距离，并且每次扫完一个点要恢复矩阵的访问状态，免得下一次扫描出错，扫到第 k 个起点的时候，把每个 cell 里面的相对于其他店的距离加起来，保持一个 min 就可以了。

时间复杂度： 2k * O(mn) ，考虑到 k 可能等于整个矩阵，其实是 O(m^2 * n^2)

空间复杂度： k * O(mn)，考虑到 k 可能等于整个矩阵，其实时 O(m^2 * n^2)

我觉得这个思路可以不用写代码了，肯定要超时的。。

这个时间复杂度和暴力解 Walls and Gates 一样，不难想到，可以试着从每个 "1" 出发，去反过来探索矩阵。 假如我们记录了这 k 个起始点，我们可以依次 bfs 每一个起始点 / 该起始点的范围，一次一个点，一次扩张一轮，当 k 个点的 “势力范围” 第一次相交的时候，就是我们要找的最优起点。有了最优起点，O(mn) 的时间显然就可以算出最短距离。

  • 问题一 : 如何保证对于固定起点的 BFS 过程中，不走回头路，而且相邻边界不重复添加；

  • 问题二：如何解决多个起点 BFS 之间的覆盖问题？

  • 问题三：对于某一个被若干个队列中边界点包围的位置，我们怎么判断每次试图访问的时候，是同一个起点的重复访问（此时跳过），还是另一个起点的回合点（此时保留）？

可以看到，在 Walls and Gates 中，这两个问题是不存在的，因为当一个位置被某个 BFS 发现之后，最短距离就确定了，后面的所有 BFS 也都不会再去访问了，一口气解决了 “相邻边界重复添加” 和 “不同起点覆盖搜索” 两个问题。

经过了半天的思考之后，依然没能找到接近 O(mn) 的解法，于是我就跑去 LC 论坛看答案了。你妹啊，你们用的也是我一开始的挫算法。。。。所以如果真是面试头一次碰到这种题，不要犹豫，就先撸个最暴力的办法再说。

痛定思痛，一次撸完AC，速度超过 89.66%

  • 开个 int[][] 记录每个位置相对于每个点的最短距离，每一个 (i , j) 的值只会在一次探索中被更新一次，取值叠加；

  • 用负数作为 flag ，代表探索进度。有两个明显的好处：

    • 剪枝，扫第 5 个起点的时候，对于 flag = -2 的位置，连扫的必要都没有；

    • 去重，每个起点的 BFS 都需要机制来避免重复添加，而 flag 是天然的状态指示，如果当前位置的 flag 和当前 BFS 的有效 flag 不相等，则直接跳过，起到了一个 undirected graph bfs 中的 0, 1, 2 状态功能~

  • 每个起点的 BFS 都会更新其所有能碰到的 “有效点” 的最短距离，一个点在一次迭代中只会被访问一次。

  • 因此最后只要扫一下 flag 矩阵，flag == curMark 的就是合理位置，找其对应的 disMap[][] 值，记录最小就可以了。

  • 另一个优化是，可以在每一轮的 BFS 过程中检查当前最短距离，省去最后收尾扫描。不过对用时影响不大就是了，下面的代码没写那部分。

    public int shortestDistance(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;

        int[][] disMap = new int[rows][cols];
        int minDis = Integer.MAX_VALUE;

        int curMark = 0;

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(grid[i][j] == 1){
                    bfs(grid, disMap, i, j, curMark);
                    curMark --;
                }
            }
        }

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(grid[i][j] == curMark) minDis = Math.min(minDis, disMap[i][j]);
            }
        }


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

    private void bfs(int[][] grid, int[][] disMap, int x, int y, int curMark){
        int rows = grid.length;
        int cols = grid[0].length;
        int distance = 1;

        Queue<int[]> queue = new LinkedList<>();
        // Just found out using curMark can save the use of visited
        queue.offer(new int[]{x, y});

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int[] cur = queue.poll();
                int curX = cur[0];
                int curY = cur[1];

                int[] xDirs = {0,0,1,-1};
                int[] yDirs = {-1,1,0,0};

                for(int j = 0; j < 4; j++){
                    int nextX = curX + xDirs[j];
                    int nextY = curY + yDirs[j];

                    if(nextX >= 0 && nextX < rows && 
                        nextY >= 0 && nextY < cols && 
                        grid[nextX][nextY] == curMark){

                        grid[nextX][nextY] = curMark - 1;
                        disMap[nextX][nextY] += distance;
                        queue.offer(new int[]{nextX, nextY});
                    }
                }
            }
            distance ++;
        }
    }
PreviousUndirected Graph, DFSNext欧拉回路，Hierholzer算法

Last updated