java如何使用BFS和DFS两种方式解岛屿数量

发布时间:2022-01-17 14:14:07 作者:清风
来源:亿速云 阅读:144

这篇文章主要为大家展示了java如何使用BFS和DFS两种方式解岛屿数量,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带大家一起来研究并学习一下“java如何使用BFS和DFS两种方式解岛屿数量”这篇文章吧。

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为例来看一下

java如何使用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,岛屿的数量加113                count++;14                //然后通过dfs把当前格子的上下左右415                //个位置为1的都要置为0,因为他们是连着16                //一起的算一个岛屿,17                dfs(grid, i, j);18            }19        }20    //最后返回岛屿的数量21    return count;22}2324//这个方法会把当前格子以及他邻近的为1的格子都会置为125public 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就是先把当前位置附近的访问一遍,就像下面这样先访问圈内的,然后再把圈放大继续访问,就像下面这样

java如何使用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,岛屿的数量加113                count++;14                //然后通过bfs把当前格子的上下左右415                //个位置为1的都要置为0,因为他们是连着16                //一起的算一个岛屿,17                bfs(grid, i, j);18            }19        }20    return count;21}2223private void bfs(char[][] grid, int x, int y) {24    //把当前格子先置为025    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}

Java的特点有哪些

Java的特点有哪些 1.Java语言作为静态面向对象编程语言的代表,实现了面向对象理论,允许程序员以优雅的思维方式进行复杂的编程。 2.Java具有简单性、面向对象、分布式、安全性、平台独立与可移植性、动态性等特点。 3.使用Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等。

以上就是关于“java如何使用BFS和DFS两种方式解岛屿数量”的内容,如果该文章对你有所帮助并觉得写得不错,劳请分享给你的好友一起学习新知识,若想了解更多相关知识内容,请多多关注亿速云行业资讯频道。

推荐阅读:
  1. java bfs实现单词最少转换次数
  2. javascript基础修炼(10)——VirtualDOM和基本DFS

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java

上一篇:java如何求幂的数字和

下一篇:vue如何用Echarts画柱状图

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》