13518219792
这篇文章主要为大家展示了java如何使用BFS和DFS两种方式解岛屿数量，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带大家一起来研究并学习一下“java如何使用BFS和DFS两种方式解岛屿数量”这篇文章吧。
10多年的尚志网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。营销型网站建设的优势是能够根据用户设备显示端的尺寸不同，自动调整尚志建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联公司从事“尚志网站设计”,“尚志网站推广”以来，每个客户项目都认真落实执行。
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为例来看一下
每个位置只要是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就是先把当前位置附近的访问一遍，就像下面这样先访问圈内的，然后再把圈放大继续访问，就像下面这样
这题使用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 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的特点有哪些 1.Java语言作为静态面向对象编程语言的代表，实现了面向对象理论，允许程序员以优雅的思维方式进行复杂的编程。 2.Java具有简单性、面向对象、分布式、安全性、平台独立与可移植性、动态性等特点。 3.使用Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等。
以上就是关于“java如何使用BFS和DFS两种方式解岛屿数量”的内容，如果该文章对你有所帮助并觉得写得不错，劳请分享给你的好友一起学习新知识，若想了解更多相关知识内容，请多多关注创新互联行业资讯频道。
