[LintCode] Number of Islands

java 5 2016-02-29 13:03
女装

Problem

Given a boolean 2D matrix, find the number of islands.

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.

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.

Note

两个for循环遍历整个矩阵,出现"1"则count++将其周围相邻的"1"全部标记为"0",用子函数mark()递归标记。

Solution

public class Solution {
    public int numIslands(boolean[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]) {
                    count++;
                    mark(grid, i, j);
                }
            }
        }
        return count;
    }
    public void mark(boolean[][]grid, int i, int j) {
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j]) {
            grid[i][j] = false;
            mark(grid, i, j-1);
            mark(grid, i-1, j);
            mark(grid, i, j+1);
            mark(grid, i+1, j);
        }
    }
}
女装
文章评论