445,BFS和DFS两种方式解岛屿数量

Wesley13
• 阅读 627

However dark and scary the world might be right now, there will be light.

无论世界现在有多黑暗,多可怕,终有一天会重现光明。

问题描述

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:

[

['1','1','1','1','0'],

['1','1','0','1','0'],

['1','1','0','0','0'],

['0','0','0','0','0']

]

输出: 1

示例 2:

输入:

[

['1','1','0','0','0'],

['1','1','0','0','0'],

['0','0','1','0','0'],

['0','0','0','1','1']

]

输出: 3

解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

DFS解决

这题让求的是岛屿的面积,二维数组中值是1的都是岛屿,如果多个1是连着的,那么他们只能算一个岛屿。

最简单的一种方式就是遍历数组中的每一个值,如果是1就说明是岛屿,然后把它置为0或者其他的字符都可以,只要不是1就行,然后再遍历他的上下左右4个位置。如果是1,说明这两个岛屿是连着的,只能算是一个岛屿,我们还要把它置为0,然后再以它为中心遍历他的上下左右4个位置……。如果是0,就说明不是岛屿,就不在往他的上下左右4个位置遍历了。这里就以示例1为例来看一下

445,BFS和DFS两种方式解岛屿数量

每个位置只要是1,先要把它置为0,然后沿着他的上下左右4个方向继续遍历,执行同样的操作,要注意边界条件的判断。代码比较简单,来看下

 1public int numIslands(char[][] grid) {
 2    //边界条件判断
 3    if (grid == null || grid.length == 0)
 4        return 0;
 5    //统计岛屿的个数
 6    int count = 0;
 7    //两个for循环遍历每一个格子
 8    for (int i = 0; i < grid.length; i++)
 9        for (int j = 0; j < grid[0].length; j++) {
10            //只有当前格子是1才开始计算
11            if (grid[i][j] == '1') {
12                //如果当前格子是1,岛屿的数量加1
13                count++;
14                //然后通过dfs把当前格子的上下左右4
15                //个位置为1的都要置为0,因为他们是连着
16                //一起的算一个岛屿,
17                dfs(grid, i, j);
18            }
19        }
20    //最后返回岛屿的数量
21    return count;
22}
23
24//这个方法会把当前格子以及他邻近的为1的格子都会置为1
25public void dfs(char[][] grid, int i, int j) {
26    //边界条件判断,不能越界
27    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
28        return;
29    //把当前格子置为0,然后再从他的上下左右4个方向继续遍历
30    grid[i][j] = '0';
31    dfs(grid, i - 1, j);//上
32    dfs(grid, i + 1, j);//下
33    dfs(grid, i, j + 1);//左
34    dfs(grid, i, j - 1);//右
35}

BFS解决

DFS就是沿着一条路径一直走下去,当遇到终止条件的时候才会返回,而BFS就是先把当前位置附近的访问一遍,就像下面这样先访问圈内的,然后再把圈放大继续访问,就像下面这样

445,BFS和DFS两种方式解岛屿数量

这题使用BFS和DFS都能解决,如果遇到位置为1的格子,只要能把他们挨着的为1的全部置为0,然后挨着的挨着的为1的位置也置为0,然后……一直这样循环下去,看下代码

 1public int numIslands(char[][] grid) {
 2    //边界条件判断
 3    if (grid == null || grid.length == 0)
 4        return 0;
 5    //统计岛屿的个数
 6    int count = 0;
 7    //两个for循环遍历每一个格子
 8    for (int i = 0; i < grid.length; i++)
 9        for (int j = 0; j < grid[0].length; j++) {
10            //只有当前格子是1才开始计算
11            if (grid[i][j] == '1') {
12                //如果当前格子是1,岛屿的数量加1
13                count++;
14                //然后通过bfs把当前格子的上下左右4
15                //个位置为1的都要置为0,因为他们是连着
16                //一起的算一个岛屿,
17                bfs(grid, i, j);
18            }
19        }
20    return count;
21}
22
23private void bfs(char[][] grid, int x, int y) {
24    //把当前格子先置为0
25    grid[x][y] = '0';
26    int n = grid.length;
27    int m = grid[0].length;
28    //使用队列,存储的是格子坐标转化的值
29    Queue<Integer> queue = new LinkedList<>();
30    //我们知道平面坐标是两位数字,但队列中存储的是一位数字,
31    //所以这里是把两位数字转化为一位数字
32    int code = x * m + y;
33    //坐标转化的值存放到队列中
34    queue.add(code);
35    while (!queue.isEmpty()) {
36        //出队
37        code = queue.poll();
38        //在反转成坐标值(i,j)
39        int i = code / m;
40        int j = code % m;
41        if (i > 0 && grid[i - 1][j] == '1') {//上
42            //如果上边格子为1,把它置为0,然后加入到队列中
43            //下面同理
44            grid[i - 1][j] = '0';
45            queue.add((i - 1) * m + j);
46        }
47        if (i < n - 1 && grid[i + 1][j] == '1') {//下
48            grid[i + 1][j] = '0';
49            queue.add((i + 1) * m + j);
50        }
51        if (j > 0 && grid[i][j - 1] == '1') { //左
52            grid[i][j - 1] = '0';
53            queue.add(i * m + j - 1);
54        }
55        if (j < m - 1 && grid[i][j + 1] == '1') {//右
56            grid[i][j + 1] = '0';
57            queue.add(i * m + j + 1);
58        }
59    }
60}

总结

这题首先要搞懂岛屿是由什么组成的,如果都是1并且挨着的话那么他们只能算一个岛屿,所以当我们找到一个岛屿的时候,首先要把他变为0,然后再把它上下左右4个方向为1的也要变成0,因为他们挨着的算是一个岛屿,接着继续再把挨着的挨着的以同样的方式遍历……。

445,BFS和DFS两种方式解岛屿数量

422,剑指 Offer-使用DFS和BFS解机器人的运动范围

417,BFS和DFS两种方式求岛屿的最大面积

409,动态规划求不同路径

397,双指针求接雨水问题

445,BFS和DFS两种方式解岛屿数量

长按上图,识别图中二维码之后即可关注。

本文分享自微信公众号 - 数据结构和算法(sjjghsf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
2年前
JS 苹果手机日期显示NaN问题
问题描述newDate("2019122910:30:00")在IOS下显示为NaN原因分析带的日期IOS下存在兼容问题解决方法字符串替换letdateStr"2019122910:30:00";datedateStr.repl
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
8个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这