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都可以解出這一道題，島嶼的數(shù)量就是numIslands()方法中進入DFS的次數(shù)。核心思路就是設(shè)置一個布爾數(shù)組記錄陸地是否訪問過，在numIslands()方法中遍歷每塊陸地，對沒有訪問過的陸地進行DFS遍歷，并把布爾數(shù)組變?yōu)?code>true，結(jié)果加1。DFS方法中，按照四個方位決定下一次訪問的位置，注意要判斷是否越界，是否為陸地且沒有被訪問過的情況。
代碼的思路已經(jīng)很清晰了，有很多可以簡化代碼的地方，比如三個特殊值判斷的if語句可以利用||短路的特性合并為一個表達式。如果允許更改傳入?yún)?shù)，那么可以不用設(shè)置布爾數(shù)組，直接將已訪問過的陸地設(shè)置為'0'即可。如果在DFS方法中判斷是否為未訪問過的陸地也可以，個人習慣，我只是覺得在numIslands()方法中判斷會減少遞歸棧使用的次數(shù)。使用BFS改寫的話，主要是在BFS方法中使用隊列作迭代，遇到符合情況的陸地就放入隊列中，迭代開始時取出來，直到隊列為空。
最重要的還是要注意參數(shù)是否為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不是四邊形，可能會出現(xiàn)錯誤，需要動態(tài)的判斷cols的值，也就是要使用grid[i].length作為內(nèi)層循環(huán)的條件。
