class Solution {
    private int[][] dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    public int numIslands(char[][] grid) {

        int r = grid.length;
        int c = grid[0].length;

        int numberIslands = 0;

        for(int i = 0; i < r; i ++){
            for(int j = 0; j < c; j ++){
                int src = i * c + j;

                if(grid[i][j] == '1'){
                    traverseBFS(grid, r, c, src);
                    numberIslands ++;
                }
            }
        }

        return numberIslands;
    }

    private void traverseBFS(char[][] grid, int r, int c, int src){
        Queue<Integer> q = new LinkedList<>();
        q.add(src);

        while(!q.isEmpty()){
            int cn = q.poll();  
            int cnr = cn / c;
            int cnc = cn % c;

            for(int d = 0; d < 4; d ++){
                int nnr = cnr + dir[d][0];
                int nnc = cnc + dir[d][1];

                if(nnr >= 0 && nnc >= 0 && nnr < r && nnc < c){
                    int nn = nnr * c + nnc;
                    if(grid[nnr][nnc] == '1'){
                        // alternative to maintaining visited array
                        grid[nnr][nnc] = '0'; 

                        q.add(nn);
                    }
                }
            }
        }
    }
}