Problem

Given a boolean 2D matrix, 0 is represented as the sea, 1 is 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.

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]
]
return 3.

思路一(bfs)

• go through each point in the matrix, and at that point we search its islands, which means we would search those points connect to the current points, and we maintain a count variable to count the number of islands.
• if we can modify the original, we can mark the visited point as 0; otherwise we need an array to record those visited points.

    public int numIslands(boolean[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]) {
                    islands++;
                    bfs (grid, i, j);
                }
            }
        }
        return islands;
    }

    private void bfs (boolean[][] grid, int x, int y) {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        grid[x][y] = false;
        while (!queue.isEmpty()) {
            Point curt = queue.poll();
            for (int i = 0; i < 4; i++) {
                Point adj = new Point(curt.x + dx[i], curt.y + dy[i]);
                if (adj.x < 0 || adj.x >= grid.length || adj.y < 0 || adj.y >= grid[0].length) continue;
                if (!grid[adj.x][adj.y]) continue;
                grid[adj.x][adj.y] = false;
                queue.offer(adj);
            }    
        }
    }

    class Point {
        int x;
        int y;
        public Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

思路二(dfs)

• go through each point in the matrix. search from the current to its adjacent points

    public int numIslands(boolean[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]) {
                    islands++;
                    // bfs (grid, i, j);
                    dfs (grid, i, j);
                }
            }
        }
        return islands;
    }

    private void dfs (boolean[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || !grid[x][y]) return;

        grid[x][y] = false;
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
        dfs(grid, x - 1, y);
    }

python(bfs)

    def numIslands(self, grid):

        if not grid or len(grid) == 0 or len(grid[0]) == 0:
            return 0
        m = len(grid)
        n = len(grid[0])

        def bfs(grid, x, y):
            queue = deque()
            queue.append((x, y))
            grid[x][y] = False

            dx = [1, -1, 0, 0]
            dy = [0, 0, 1, -1]

            while len(queue) > 0:
                curt = queue.popleft();
                for i in range(4):
                    next = (curt[0] + dx[i], curt[1] + dy[i])
                    if next[0] < 0 or next[0] >= m or next[1] < 0 or next[1] >= n or not grid[next[0]][next[1]]:
                        continue
                    grid[next[0]][next[1]] = False
                    queue.append((next[0], next[1]))

        count = 0
        for i in range(m):
            for j in range(n):
                # print grid[i][j]
                if grid[i][j]:
                    bfs(grid, i, j)
                    count += 1

        return count