Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:11110110101100000000
Output: 1Example 2:
Input:11000110000010000011
Output: 3
难度：medium
题目：给定一个由 1 和 0 组成的二维表格，1 表示陆地 0 表示水域，统计陆地数。一块陆地是由水域包围且由水平和垂直陆地连结而成。你可以假定表格的四边都由水域包围。
思路：递归遍历，将遍历过的位置标记出来。
Runtime: 3 ms, faster than 100.00% of Java online submissions for Number of Islands.
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (‘1’ == grid[i][j]) {
colorGrid(grid, i, j);
count++;
}
}
}
return count;
}
private void colorGrid(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length
|| j < 0 || j >= grid[i].length
|| ‘0’ == grid[i][j] || ‘X’ == grid[i][j]) {
return;
}
grid[i][j] = ‘X’;
colorGrid(grid, i + 1, j);
colorGrid(grid, i – 1, j);
colorGrid(grid, i, j + 1);
colorGrid(grid, i, j – 1);
}
}