lintcode 677. 大岛的数量 dfs

r囧r小猫 2023-07-24 14:38 75阅读 0赞

给一个布尔类型的二维数组, 0 表示海, 1 表示岛。如果两个1是相邻的,那么我们认为他们是同一个岛.我们只考虑 上下左右 相邻.  
找到大小在 k 及 k 以上的岛屿的数量

样例
    样例1
    
    输入：
    [[1,1,0,0,0],[0,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,0,0,1]]
    2
    输出： 2
    解释：
    2D网络为
    [
      [1, 1, 0, 0, 0],
      [0, 1, 0, 0, 1],
      [0, 0, 0, 1, 1],
      [0, 0, 0, 0, 0],
      [0, 0, 0, 0, 1]
    ]
    一共有两个大小为3的岛。
    样例2
    
    输入：
    [[1,0],[0,1]]
    1
    输出： 2

思路：深度搜索，查询一个true周围有多少个true连成岛屿，大小是否符合要求即可。  
注意：查询后的true要修改为false，防止多次查询同一个true造成死循环

class Solution {
        
    public:
        /**
         * @param grid: a 2d boolean array
         * @param k: an integer
         * @return: the number of Islands
         */
        int numsofIsland(vector<vector<bool>> &grid, int k) {
        
            // Write your code here
            if(grid.size()<=0) return 0;
            if(grid[0].size()<=0) return 0;
            int res=0;
            for (int i = 0; i < grid.size(); i++) {
        
                for(int j = 0; j < grid[i].size();j++)
                {
        
                    int cnt=0;
                    if(grid[i][j]==true) dfs(grid,i,j,cnt);
                    if(cnt>=k) res++;
                }
            }
            return res;
        }
        void dfs(vector<vector<bool>> &grid,int row,int col,int &cnt)
        {
        
            if(row<0||col<0||row>=grid.size()||col>=grid[0].size()) return;
            else
            {
        
                if(grid[row][col]==true) 
                {
        
                    cnt++;
                    grid[row][col]=false;
                    dfs(grid,row+1,col,cnt);
                    dfs(grid,row-1,col,cnt);
                    dfs(grid,row,col+1,cnt);
                    dfs(grid,row,col-1,cnt);
                }
                else return;
            }
        }
    };