LeetCode <BT> 200. Number of Islands

原创

大学里的混子

修改于 2018-11-26 14:52:50

4140

修改于 2018-11-26 14:52:50

文章被收录于专栏：LeetCodeLeetCode

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

题目大意：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 删除。

其他

登录后参与评论

0 条评论

热度