⭐⭐⭐⭐⭐【多源BFS】LeetCode 1162. As Far from Land as Possible

主要问题出在忽视了时间复杂度，以海域为单位进行BFS了，应该是陆地才对

题目描述

知识点

网格型多源BFS

结果

实现

码前思考

1. 我刚开始觉得这个题目好简单，典型的网格搜索BFS嘛，于是我就遍历每一个海域使用BFS，结果就超时了。。。代码如下：
   超时代码——以海域为源点进行搜索

   //感觉使用bfs来解题
   //所谓的曼哈顿距离可以使用bfs的层数来表示~
   //If no land or water exists in the grid, return -1.
   class Solution {
   private:
       //坐标数组
       int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//数组初始化居然只能用{{}}
       vector<vector<bool>> vis;
       int len;
       
   public:
   
       int maxDistance(vector<vector<int>>& grid) {
           len = grid.size();
           int maxVal=-1;
           //对每一个网格进行广度优先搜索
           for(int i=0;i<len;i++){
               for(int j=0;j<len;j++){
                   if(grid[i][j]==0){
                       int curVal = bfs(i,j,grid);
                       if(curVal > maxVal){
                           maxVal = curVal;
                       }
                   }
               }
           }
           return maxVal;
       }
   
       int bfs(int x,int y,vector<vector<int>>& grid){
           int level=-1;
           queue<int> q;
           vis.assign(len,vector<bool>(len,false));
   
           int pos = x*1000+y;//hash记录坐标
           q.push(pos);
           vis[x][y] = true;
   
           while(!q.empty()){
               level++;
               int size =q.size();
               for(int i=0;i<size;i++){
                   int pos = q.front();
                   q.pop();
                   int curX = pos/1000;
                   int curY = pos%1000;
                   if(grid[curX][curY]==1){
                       return level;
                   }else{
                       for(int i=0;i<4;i++){
                           int adjX = curX + dir[i][0];
                           int adjY = curY + dir[i][1];
                           if(judge(adjX,adjY)){
                               q.push(adjX*1000+adjY);
                               vis[adjX][adjY] = true;
                           }
                       }
                   }
               }
           }
           return -1;
       }
   
       bool judge(int x,int y){
           if(x<0||x>=len||y<0||y>=len){
               return false;
           }
           if(vis[x][y]){
               return false;
           }
           return true;
       }
   };
   

2. 后来，我看官方的题解才发现，以海域为源点的时间复杂度最坏情况下是 $O(n^4)$O(n4)，难怪会超时。
3. 再然后，我看题解上说这个一个以陆地为源点的多源BFS，要以陆地为源点！这样，每次BFS都类似于图的BFS，设置一个vis数组标记是否访问，那么最后一层的就是最远的那个海域了。
4. 为什么能确保都是离每个海域最近的陆地呢？我看大神们是说可以把所有的陆地连接到一个超级节点那里，我觉得很有道理诶~如下图：
   
5. 对于图的BFS也是一样滴～ 与Tree的BFS区别如下：
   1、tree只有1个root，而 图可以有多个源点，所以首先需要把多个源点都入队。
   2、tree是有向的因此不需要标志是否访问过， 而对于无向图来说，必须得标志是否访问过！
   并且为了防止某个节点多次入队，需要在入队之前就将其设置成已访问！

代码实现

//感觉使用bfs来解题
//所谓的曼哈顿距离可以使用bfs的层数来表示~
//If no land or water exists in the grid, return -1.
class Solution {
private:
    //坐标数组
    int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//数组初始化居然只能用{{}}
    vector<vector<bool>> vis;
    int len;
    
public:
    int maxDistance(vector<vector<int>>& grid) {
        len = grid.size();
        int level=-1;
        queue<int> q;
        vis.assign(len,vector<bool>(len,false));

        //将所有的陆地入队列，然后遍历所有的海域，这样可以转换问题
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(grid[i][j]==1){
                    q.push(i*1000+j);
                    vis[i][j] = true;
                }
            }
        }

        //然后进行遍历
        while(!q.empty()){
            level++;
            int size =q.size();
            for(int i=0;i<size;i++){
                int pos = q.front();
                q.pop();
                int curX = pos/1000;
                int curY = pos%1000;
                for(int i=0;i<4;i++){
                    int adjX = curX + dir[i][0];
                    int adjY = curY + dir[i][1];
                    if(judge(adjX,adjY,grid)){
                        q.push(adjX*1000+adjY);
                        vis[adjX][adjY] = true;
                    }
                }
            }
        }       

        return level==0?-1:level;
    }

    bool judge(int x,int y,vector<vector<int>>& grid){
        if(x<0||x>=len||y<0||y>=len||vis[x][y]||grid[x][y]==1){
            return false;
        }
        return true;
    }
};

码后反思

1. 懂得了多源BFS这样一种概念，原来题目并没有自己想得那么简单啊。。。不要看见海域就是海域，要能够分析时间复杂度呢！
2. 现在才发现，数组的初始化必须要用{}，不能使用[]，以前只是手感告诉自己要用{}，今天没手感，发现用[]就报错了。。。