//
// Created by 高森森 on 2022/2/10.
//

#ifndef LEETCODE_SOLUTION31_H
#define LEETCODE_SOLUTION31_H
#include<iostream>
#include<vector>
using namespace std;

class Solution31 {
public:
    pair<int,int>direction[4]={{-1,0},{1,0},{0,-1},{0,1}};
    int closedIsland(vector<vector<int>>& grid) {
        int row=grid.size();
        int col=grid[0].size();
        int ans=0;
        if(row<3||col<3)
            return ans;
        vector<vector<bool>>visited(row,vector<bool>(col,0));
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++){
                if(grid[i][j]==0&&!visited[i][j])
                {
                    if(dfs(i,j,row,col,grid,visited))
                        ans++;
                }
            }
        return ans;
    }
    bool dfs(int x,int y,int row, int col,vector<vector<int>>&grid, vector<vector<bool>>&visited){
        if(x>=row||x<0||y>=col||y<0)
            return false;
        if(grid[x][y]==1||visited[x][y]==1)
            return true;

         visited[x][y]=1;
//        bool flag = true;
        for (int i=0;i<4;i++){
            if(!dfs(x+direction[i].first,y+direction[i].second,row,col,grid,visited))
                return false;
        }
        return true;
    }
    int closedIsland2(vector<vector<int>>& grid) {
        int row=grid.size();
        int col=grid[0].size();
        int ans=0;
        if(row<3||col<3)
            return ans;
        vector<vector<bool>>visited(row,vector<bool>(col,0));
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++){
                if(grid[i][j]==0)
                {
                    if(dfs2(i,j,row,col,grid))
                        ans++;
                }
            }
        return ans;
    }
    bool dfs2(int x,int y,int row, int col,vector<vector<int>>&grid){
        if(x<0||x>=row||y<0||y>=col)
            return false;
        if(grid[x][y]==1)
            return true;
        grid[x][y]=1;
        bool flag= true;
        for (int i=0;i<4;i++){
            if(!dfs2(x+direction[i].first,y+direction[i].second,row,col,grid))
                flag= false;
        }
        return flag;
    }

};


#endif //LEETCODE_SOLUTION31_H