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
题目大意:1代表陆地,0代表水域,求陆地的数量。
思路:严格的说这个题目并不算是一个回溯的算法,因为没有回溯的过程,应该是一个深度优先的方法,但是过程与回溯的算法思路是一样。
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);
}
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。