# 200. Number of Islands (BFS)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mj9zFPecvB1NqvlRJ9R%2F-Mj9zeaVvNInmViW_R9w%2Fimage.png?alt=media\&token=363c6744-2dbe-4c13-acf3-baa1476a3c63)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mj9zFPecvB1NqvlRJ9R%2F-Mj9zgtJtVFZTSWT7V3U%2Fimage.png?alt=media\&token=63d5799f-8798-494f-8c30-ece350d1b90a)

time: O(m\*n)

space:O(min(m,n))

```java
class Solution {
    private int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public int numIslands(char[][] grid) {
        
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        boolean vistited[][] = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !vistited[i][j]) {
                    BFS(grid, i , j, vistited);
                    count++;
                }
            }
        }
        return count;
    }
    private void BFS(char[][] grid, int x , int y, boolean vistited[][]) {
                
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{x, y});
        vistited[x][y] = true;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++ ) {
                int cor[] = queue.poll();
                int corX = cor[0];
                int corY = cor[1];
                for (int direction[] : directions) {
                    int newCorX = corX + direction[0];
                    int newCorY = corY + direction[1];
                    if (isValid(grid, vistited, newCorX, newCorY)) {
                        queue.offer(new int[]{newCorX, newCorY});
                        vistited[newCorX][newCorY] = true;
                    }
                }
            }
            
        }
    }
    private boolean isValid(char[][] grid, boolean vistited[][], int x, int y) {
        return (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && !vistited[x][y] && grid[x][y] == '1');
    }
}
```
