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
Java Solution:
final int[][] go={
{1,0},
{0,1},
{-1,0},
{0,-1}
};
boolean[][] visited;
public int numIslands(char[][] grid) {
if(grid==null) return 0;
if(grid.length==0) return 0;
if(grid[0].length==0) return 0;
int rows=grid.length;
int cols=grid[0].length;
visited=new boolean[rows][cols];
int res=0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(grid[i][j]=='1'&&!visited[i][j]){
res++;
visited[i][j]=true;
floodFill(grid,i,j,rows,cols);
}
}
}
visited=null;
return res;
}
private void floodFill(char[][] grid,int x,int y,int rows,int cols){
for(int i=0;i<4;i++){
int nextx=x+go[i][0];
int nexty=y+go[i][1];
if(nextx>=rows||nextx<0||nexty>=cols||nexty<0) continue;
if(grid[nextx][nexty]=='0') continue;
if(!visited[nextx][nexty]){
visited[nextx][nexty]=true;
floodFill(grid,nextx,nexty,rows,cols);
}
}
return;
}
时间复杂度：O(n*m)
空间复杂度：O(n*m)
这是一道比较基本的FloodFill算法题，用DFS或者BFS都可以解出这一道题，岛屿的数量就是numIslands()方法中进入DFS的次数。核心思路就是设置一个布尔数组记录陆地是否访问过，在numIslands()方法中遍历每块陆地，对没有访问过的陆地进行DFS遍历，并把布尔数组变为true，结果加1。DFS方法中，按照四个方位决定下一次访问的位置，注意要判断是否越界，是否为陆地且没有被访问过的情况。
代码的思路已经很清晰了，有很多可以简化代码的地方，比如三个特殊值判断的if语句可以利用||短路的特性合并为一个表达式。如果允许更改传入参数，那么可以不用设置布尔数组，直接将已访问过的陆地设置为'0'即可。如果在DFS方法中判断是否为未访问过的陆地也可以，个人习惯，我只是觉得在numIslands()方法中判断会减少递归栈使用的次数。使用BFS改写的话，主要是在BFS方法中使用队列作迭代，遇到符合情况的陆地就放入队列中，迭代开始时取出来，直到队列为空。
最重要的还是要注意参数是否为null，还是0长以及下一次访问的位置是否会越界的问题。
测试用例
Case1:
11000
11000
00100
00011
Answer: 3
Case2:
null
Answer: 0
Case3:
[]
Answer: 0
Case4:
111
111
111
Answer: 9
Case5:
000
000
000
Answer: 0
如果gird map不是四边形，可能会出现错误，需要动态的判断cols的值，也就是要使用grid[i].length作为内层循环的条件。
