class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1') return;
        grid[i][j] = '2';
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }

        return result;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        
        int result = 0;
        int m = grid.size();
        int n = grid[0].size();


        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    ++result;
                    queue<pair<int,int>> que;
                    que.push({i, j});
                    grid[i][j] = '2';

                    while(!que.empty()) {
                        auto node = que.front();
                        que.pop();
                        int row = node.first;
                        int col = node.second;
                        if(row-1 >= 0 && grid[row-1][col] == '1') {
                            que.push({row-1, col});
                            grid[row-1][col] = '2';
                        }
                        if(row+1 < m && grid[row+1][col] == '1') {
                            que.push({row+1, col});
                            grid[row+1][col] = '2';
                        }
                        if(col-1 >= 0 && grid[row][col-1] == '1') {
                            que.push({row, col-1});
                            grid[row][col-1] = '2';
                        }
                        if(col+1 < n && grid[row][col+1] == '1') {
                            que.push({row, col+1});
                            grid[row][col+1] = '2';
                        }
                    }
                    
                }
            }
        }

        return result;
    }
};