[数据结构与算法]Leecode 1254. 统计封闭岛屿的数目 DFS

原题链接：Leecode 1254. 统计封闭岛屿的数目
这么简单一道题，又粗心，&&写成&，&写成&&，我要吐了，浪费我两个小时找不出来错。。。


DFS

class Solution {
public:
    bool dfs(vector<vector<int>>& grid,int i,int j)
    {
        int m=grid.size(),n=grid[0].size();
        grid[i][j]=1;
        bool f=true;
        if(i==0 || i==m-1 || j==0 || j==n-1) f=false;
        if(i && !grid[i-1][j]) f=f & dfs(grid,i-1,j);
        if(i+1<m && !grid[i+1][j]) f=f & dfs(grid,i+1,j);
        if(j && !grid[i][j-1]) f=f & dfs(grid,i,j-1);
        if(j+1<n && !grid[i][j+1]) f=f & dfs(grid,i,j+1);
        return f;
    }
    int closedIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int res=0;
        for(int i=1;i<m-1;i++)
        {
            for(int j=1;j<n-1;j++)
            {
                if(grid[i][j]==0)
                {
                    if(dfs(grid,i,j)) res++;
                }
            }
        }
        return res;
    }
};

DFS（简洁一些）

class Solution {
public:
    int x[4]={-1,1,0,0};
    int y[4]={0,0,-1,1};
    bool dfs(vector<vector<int>>& grid,int i,int j)
    {
        int m=grid.size(),n=grid[0].size();
        bool f=true;
        if(i<0 || i>m-1 || j<0 || j>n-1 || grid[i][j]) return f;
        grid[i][j]=1;
        if(i==0 || i==m-1 || j==0 || j==n-1) f=false;
        for(int k=0;k<4;k++)
        {
            f&=dfs(grid,i+x[k],j+y[k]);
        }
        return f;
    }
    int closedIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int res=0;
        for(int i=1;i<m-1;i++)
        {
            for(int j=1;j<n-1;j++)
            {
                if(grid[i][j]==0)
                {
                    if(dfs(grid,i,j)) res++;
                }
            }
        }
        return res;
    }
};

BFS

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int res=0;
        for(int i=1;i<m-1;i++)
        {
            for(int j=1;j<n-1;j++)
            {
                if(grid[i][j]==0)
                {
                    grid[i][j]=1;
                    queue<pair<int,int>> q;
                    q.push({i,j});
                    bool f=true;
                    while(!q.empty())
                    {
                        auto node=q.front();
                        q.pop();
                        int x=node.first,y=node.second;
                        if(x==0 || x==m-1 || y==0 || y==n-1 ) f=false;
                        if(x && !grid[x-1][y]) 
                        {
                            q.push({x-1,y}); grid[x-1][y]=1;
                        } 
                        if(x+1<m && !grid[x+1][y])
                        {
                            q.push({x+1,y}); grid[x+1][y]=1;
                        }
                        if(y && !grid[x][y-1])
                        {
                            q.push({x,y-1}); grid[x][y-1]=1;
                        }
                        if(y+1<n && !grid[x][y+1])
                        {
                            q.push({x,y+1}) ; grid[x][y+1]=1;
                        }
                    }
                    if(f) res++;
                }
            }
        }
        return res;
    }
};

2022深度学习开发者峰会

5月20日13:00让我们相聚云端，共襄盛会！