区块链技术博客
www.b2bchain.cn

200. 岛屿数量 BFS

这篇文章主要介绍了200. 岛屿数量 BFS,通过具体代码讲解8515并且分析了200. 岛屿数量 BFS的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了200. 岛屿数量 BFS。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8515.html。具体如下:

https://www.b2bchain.cn/6172.html 

 //给你一个由 '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 //解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。 //  // Related Topics 深度优先搜索 广度优先搜索 并查集   import java.util.LinkedList;  //leetcode submit region begin(Prohibit modification and deletion) class Solution {     public int numIslands(char[][] grid) {          //BFS省空间复杂度         int row=grid.length;         if(row==0) return 0;         int col=grid[0].length;          int[][] directions={{-1, 0}, {0, -1}, {1, 0}, {0, 1}};          int ans=0;         //是否访问过该节点         boolean[][] visted=new boolean[row][col];         for (int i = 0; i <row ; i++) {             for (int j = 0; j <col ; j++) {                    //这个地方为'1' 注意输入为char数组                  //把与之相连的为1的位置全部遍历完,构成整个一个小岛                  //后面都在这个IF内                   if(grid[i][j]=='1' && visted[i][j]==false) {                       LinkedList<Integer> queue=new LinkedList<>();                       int index = i * col + j;                       queue.addLast(index);                       visted[i][j] = true;                       ans++;                         while (!queue.isEmpty()) {                           int tmp = queue.removeFirst();                           int curr = tmp / col;                           int curc = tmp % col;                           for (int k = 0; k < 4; k++) {                              int  newcurc = curc + directions[k][0];                              int  newcurr = curr + directions[k][1];                               if (newcurc >= 0 && newcurc < col && newcurr >= 0 && newcurr < row && grid[newcurr][newcurc] == '1' && visted[newcurr][newcurc] == false) {                                    queue.addLast(newcurc + newcurr * col);                                   visted[newcurr][newcurc] = true;                               }                           }                       }                   }               }         }       return ans;     } } //leetcode submit region end(Prohibit modification and deletion) 

 

本文地址https://www.b2bchain.cn/8515.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 200. 岛屿数量 BFS
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们