class Solution {
public:
    int result = 0;
    int m =0 ,n=0;
    int dir[4][2] = {0,1, 0,-1 , -1,0 , 1,0};
    void dfs(vector<vector<char>>& grid , vector<vector<bool>> &path , int x , int y)
    {
        for(int i=0 ; i<4 ;i++)
        {
            int next_x = x + dir[i][0];
            int next_y = y + dir[i][1];
            if(next_x<0||next_x>=m||next_y<0||next_y>=n) continue;
            else if( path[next_x][next_y] == false && grid[next_x][next_y] == '1') 
            {   
                path[next_x][next_y] = true;
                dfs(grid,path,next_x,next_y);
            }
        }
        return;
    }
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> path( m , vector<bool>( n ,false) );
        for(int i=0 ; i<m ;i++)
        {
            for(int j=0 ; j<n ;j++)
            {
                if(path[i][j] == false && grid[i][j] == '1')
                {
                    result++;
                    path[i][j] = true;
                    dfs(grid,path,i,j);
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int result = 0;
    int m =0 ,n=0;
    int dir[4][2] = {0,1, 0,-1 , -1,0 , 1,0};
    void bfs(vector<vector<char>>& grid , vector<vector<bool>> &path , int x , int y)
    {
        queue<pair<int,int>> my_que;
        my_que.push({x,y});
        path[x][y] = true;
        while(my_que.size() != 0)
        {
            pair<int,int> cur = my_que.front();
            my_que.pop();
            for(int i=0 ; i<4 ;i++)
            {
                int next_x = cur.first + dir[i][0];
                int next_y = cur.second + dir[i][1];
                if(next_x<0||next_x>=m||next_y<0||next_y>=n) continue;
                else if( path[next_x][next_y] == false && grid[next_x][next_y] == '1') 
                {   
                    my_que.push({next_x,next_y});
                    path[next_x][next_y] = true;
                }
            }
        }
        return;
    }
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> path( m , vector<bool>( n ,false) );
        for(int i=0 ; i<m ;i++)
        {
            for(int j=0 ; j<n ;j++)
            {
                if(path[i][j] == false && grid[i][j] == '1')
                {
                    result++;
                    path[i][j] = true;
                    bfs(grid,path,i,j);
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int m,n;
    int dir[4][2] = {0,-1,0,1,-1,0,1,0};
    void dfs(vector<vector<char>>& grid ,vector<vector<bool>> &path , int i , int j)
    {
        for(int x=0 ; x<4 ;x++)
        {
            int next_i = i + dir[x][0];
            int next_j = j + dir[x][1];
            if(next_i<0||next_i>=m||next_j<0||next_j>=n) continue;
            if(path[next_i][next_j] == false && grid[next_i][next_j] == '1')
            {
                path[next_i][next_j] = true;
                dfs(grid,path,next_i,next_j);
            }
        }
        return;
    }
    int numIslands(vector<vector<char>>& grid) {
        int result = 0;
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> path(m,vector<bool>(n,false));
        for(int i=0 ; i<m ;i++)
        {
            for(int j=0 ; j<n ;j++)
            {
                if(grid[i][j] == '1' && path[i][j] == false)
                {
                    path[i][j] = true;
                    result++;
                    dfs(grid,path,i,j);
                }
            }
        }
        return result;
    }
};