# 200. Number of Islands

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:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

# 解法：

public boolean isValidArea(int x,int y,char[][] grid){
return x>=0&&x<grid.length&&y>=0&&y<grid[0].length;
}

public int numIslands(char[][] grid) {
if (grid==null||grid.length==0||grid[0].length==0) return 0;
boolean [][] visit = new boolean[grid.length][grid[0].length];
int [][] step = {
{-1,0},
{0,1},
{1,0},
{0,-1}
};
int res = 0 ;
for (int i = 0;i<grid.length;i++){
for (int j = 0; j<grid[0].length;j++){
if (grid[i][j] == '1'&&!visit[i][j]){
res++;
dfs(grid,i,j,step,visit);
}
}
}
return res;
}

public void dfs(char[][] grid,int x,int y,int[][] step,boolean[][] visit){
visit[x][y] = true;
for (int i = 0;i<4;i++){
int xnew = x+step[i][0];
int ynew = y+step[i][1];
if (isValidArea(xnew,ynew,grid)&&!visit[xnew][ynew]&&grid[xnew][ynew] == '1'){
dfs(grid,xnew,ynew,step,visit);
}
}
}

143 篇文章21 人订阅

0 条评论

## 相关文章

3457

2158

19110

### 【算法】希尔排序学习笔记

【参考资料】 《算法（第4版）》         — — Robert Sedgewick， Kevin Wayne 在本篇笔记里，我从简单的插入排序，到希尔排...

2228

3006

1694

### POJ--3321 Apple Tree(树状数组+dfs(序列)）

Apple Tree Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 2...

3927

35013

793

22610