地图分析--多源BFS

0x01.问题

你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。

提示：1 <= grid.length == grid[0].length <= 100 grid[i][j] 不是 0 就是 1

输入示例：[[1,0,1],[0,0,0],[1,0,1]]
输出示例：2
解释：海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。

注：此题来源于Leetcode

C++函数形式：    int maxDistance(vector<vector<int>>& grid) 

0x02.简要分析

读题，清楚题目的一些重要含义：

• 要找的是距离陆地最远的海洋区，离最近的陆地区域的距离。
• 距离是曼哈顿距离，可以理解为从一个点走到另一个点的步数。

由于既涉及最远，又涉及最近，所以我们肯定不能像往常一样，去搜索最远的，然后再找最近的，因为最远的可能有多种相同，而最近可能唯一，所以这样正常的去搜索肯定是不可以的。

我们可以换一种思路，逆向思考一下，如果我们找到每一片海洋到陆地的最近距离，再取里面的最大值，是不是就满足条件了，所以我们有了第一种思路：

• 遍历grid，只要遇到海洋就去搜索。
• 搜索该片海洋离陆地的最近距离，返回条件就是，只要在搜索的过程中遇到了陆地，就说明那个是最近距离，每次搜索的时候记录步数，遇到陆地时，只要返回步数就行了。
• 最后取所有海洋离陆地最近距离的最大值。

这种思路可以解决这个问题，但并不是最好的，我们可以考虑使用多源BFS来解决。

多源BFS就是源点不唯一，是多个，其实原理也是一样的，不过效率高的多。

多个点同时遍历，其实题目中的这个距离就是我们最终遍历的最大次数。

• 解释一下：所有陆地每次往边上移动一格，最终遍历完的时候，应该是所有海洋都遍历完了的，那么最后一次遍历到的海洋就是离陆地最远的，因为要走最多的步数才能遍历到，遍历的次数就是这片海洋到陆地的最短距离，因为有一片陆地只移动了这么多次就遍历到了这片海洋。

我们的整体思路就是：

• 先把所有的陆地入队。
• 用ans'记录遍历的次数，初始为-1，因为第一次是遍历陆地，应该为0。
• 直到所有海洋遍历完，返回ans。

0x03.解决代码–普通BFS

class Solution {
public:
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };   
    struct goStep{
        int x;
        int y;
        int step;
    };
    int findMin(vector<vector<int>>& grid,int x,int y){
        bool visited[101][101];
        memset(visited, 0, sizeof visited);
        queue<goStep> queue;
        queue.push({x,y,0});
        visited[x][y]=true;
        while(!queue.empty()){
            auto p=queue.front();
            queue.pop();
            for(int i=0;i<4;i++){
                int next_x=p.x+dx[i];
                int next_y=p.y+dy[i];
                if(next_x<0||next_y<0||next_x==grid.size()||next_y==grid.size()) continue;
                if(visited[next_x][next_y]) continue;
                queue.push({next_x,next_y,p.step+1});
                visited[next_x][next_y]=true;
                if(grid[next_x][next_y]==1) return p.step+1;
            }

        }
        return -1;
    }
    int maxDistance(vector<vector<int>>& grid) {
        int ans=-1;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid.size();j++){
                if(grid[i][j]==0) ans=max(ans,findMin(grid,i,j));
            }
        }
        return ans;
    }
};

0x04.解决代码–多源BFS

class Solution {
public:
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };   
    struct goStep{
        int x;
        int y;
    };

    int maxDistance(vector<vector<int>>& grid) {
        int n=grid.size();
        queue<goStep> queue;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1) queue.push({i,j});
            }
        }
        if(queue.size()==0||queue.size()==n*n) return -1;
        int ans=-1;
        while(!queue.empty()){
            ans++;
            int k=queue.size();
            while(k--){
                auto p=queue.front();queue.pop();
                for(int i=0;i<4;i++){
                    int next_x=p.x+dx[i];
                    int next_y=p.y+dy[i];
                    if(next_x<0||next_y<0||next_x==n||next_y==n) continue;
                    if(grid[next_x][next_y]!=0) continue;
                    grid[next_x][next_y]=-1;//沉岛效应
                    queue.push({next_x,next_y});
                }
            }
        }
        return ans;
    }
};

• 二者差距其实非常大！！！
• 在时间和空间上，多源BFS都优于方法一数十倍！！！

ATFWUS --Writing By 2020–03–29