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:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
图的第一道题。。。看了太阁的视频，代码写的晦涩难懂。。。然后看了下top solution，真的是有水平的。。。不过也许太阁的代码有普适性吧，并没有好好研究。。。
思想主要就是用DFS的方法，遇到一个点就把它相关的点都遍历，把1替换成0来标记自己遍历过了。其实很简单，看来自己之前的畏难心里重了。
public class Solution { private int m; private int n; public int numIslands(char[][] grid) { if (grid == null) { return 0; } m = grid.length; if (m == 0) { return 0; } int count = 0; n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == ‘1‘) { dfs(grid, i, j); count++; } } } return count; } public void dfs(char[][] grid, int i, int j) { if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != ‘1‘) { return; } grid[i][j] = ‘0‘; dfs(grid, i - 1, j); dfs(grid, i + 1, j); dfs(grid, i, j - 1); dfs(grid, i, j + 1); } }
不过用DFS有stack over flow的风险，所以推荐用BFS或者union find，这两个方法以后再写。。。到时候回顾一下。。。
原文：http://www.cnblogs.com/aprilyang/p/6364098.html