class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int N = grid.size();
        int M = grid[0].size();
        vector<vector<int>> visited(N, vector<int>(M, 0));
        queue<pair<int,int>> q;
        int count = 0;

        for (int r = 0; r < N; r++) {
            for(int c = 0; c < M; c++) {
                if(grid[r][c] == '1' && visited[r][c] == 0) {
                    count++;
                    q.push({r, c});

                    while(!q.empty()) {
                        pair<int,int> temp = q.front();
                        q.pop();
                        int rn = temp.first;
                        int cn = temp.second;
                        visited[rn][cn] = 1;

                        vector<pair<int,int>> directions = {{rn+1,cn}, {rn,cn+1}, {rn-1,cn}, {rn,cn-1}};

                        for (auto t : directions) {
                            int rn = t.first;
                            int cn = t.second;

                            if(rn >= 0 && rn < N && cn >= 0 && cn < M && grid[rn][cn] == '1' && visited[rn][cn] == 0) {
                                q.push({rn, cn});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};