LeetCode <BT> 200. Number of Islands

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);
        }
    }
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:表达式以及运算符

正文之前 好久没写了啊!!感觉自己都已经不爱简书了。不过其实我的《C++ Primer》已经看到400多页了。然而网络笔记还停留在120页,这个很骚啊,意味着我...

3457
来自专栏老马说编程

(93) 函数式数据处理 (下) / 计算机程序的思维逻辑

上节初步介绍了Java 8中的函数式数据处理,对于collect方法,我们只是演示了其最基本的应用,它还有很多强大的功能,比如,可以分组统计汇总,实现类似数据库...

2158
来自专栏禁心尽力

Java Collection知识总结

首先说说java中常用的集合容器:ArrayList,LinkedList,Vector,HashMap,Hashtable,HashSet,TreeSet。【...

19110
来自专栏彭湖湾的编程世界

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

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

2228
来自专栏python读书笔记

python 数据分析基础 day9-datetime类型常用对象以及函数日期类型的运算

今天是读《python数据分析基础》的第9天,今天将通过python的date模块来总结日期类型。 常用对象以及函数 对象 可通过date模块创建创建以下对象:...

3006
来自专栏北京马哥教育

看完这篇文章还不懂Python中的闭包,请拍死小编

1694
来自专栏算法修养

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

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

3927
来自专栏逸鹏说道

我为NET狂面试题-基础篇-答案

面向过程: 答案:图片只贴核心代码,完整代码请打开解决项目查看 (答案不唯一,官方答案只供参考,若有错误欢迎提出~) 99乘法表 https://githu...

35013
来自专栏华章科技

从Zero到Hero,一文掌握Python关键代码

首先,什么是 Python?根据 Python 创建者 Guido van Rossum 所言,Python 是一种高级编程语言,其设计的核心理念是代码的易读性...

793
来自专栏java达人

Java 8 Stream 教程 (二)

作者:Benjamin 译者:java达人 来源:http://winterbe.com/posts/2014/07/31/java8-stream-tuto...

22610

扫码关注云+社区