Given a boolean 2D matrix,0is represented as the sea,1is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Have you met this question in a real interview?

Yes

Example

Given graph:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

return3.

1. BFS

double for loop to go through the matrix and for each true point(island point) that hasn't been visited(can use extra array to remember, or simply turn it to 0) do a BFS that go to direct four direction until the queue is empty.

 public int numIslands(boolean[][] grid) {
        int sum = 0;
        if (grid == null || grid.length == 0 || grid[0] == null || grid.length == 0) {
            return sum;
        }
        int[][] isVisited = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length ; j++) {

                if (grid[i][j] && isVisited[i][j] == 0) {
                    isVisited[i][j] = 1;
                    bfs(grid, i, j, isVisited);
                    sum++;
                }
            }

        }
        return sum;
    }

    public void bfs(boolean[][] grid, int i, int j, int[][] isVisited) {
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.offer(new Pair(i, j));
        while (!queue.isEmpty()) {
            int size = queue.size();
            Pair cur = queue.poll();

            while (size > 0) {
                if (cur.y + 1 < grid.length && grid[cur.y + 1][cur.x] && isVisited[cur.y + 1][cur.x] == 0) {

                    isVisited[cur.y + 1][cur.x] = 1;
                    queue.offer(new Pair(cur.y + 1, cur.x));

                }

                if (cur.y - 1 >= 0 && grid[cur.y - 1][cur.x] && isVisited[cur.y - 1][cur.x] == 0) {

                    isVisited[cur.y - 1][cur.x] = 1;
                    queue.offer(new Pair(cur.y - 1, cur.x));

                }

                if (cur.x + 1 < grid[0].length && grid[cur.y][cur.x + 1] && isVisited[cur.y][cur.x + 1] == 0) {

                    isVisited[cur.y][cur.x + 1] = 1;
                    queue.offer(new Pair(cur.y, cur.x + 1));
                }

                if (cur.x - 1 >= 0 && grid[cur.y][cur.x - 1] && isVisited[cur.y][cur.x - 1] == 0) {

                    isVisited[cur.y][cur.x - 1] = 1;
                    queue.offer(new Pair(cur.y, cur.x - 1));
                }

                size--;
            }

        }
    }