[LintCode] Number of Islands(岛屿个数)
of number 个数 lintcode 岛屿
2023-09-27 14:20:35 时间
描述
给一个01矩阵,求不同的岛屿的个数。
0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
样例
在矩阵:
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
中有 3
个岛。
代码
GitHub 的源代码,请访问下面的链接:
package com.ossez.lang.tutorial.tests.lintcode; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /** * <p> * 433 * <ul> * <li>@see <a href= * "https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands">https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands</a> * <li>@see<a href="https://www.lintcode.com/problem/number-of-islands/">https://www.lintcode.com/problem/number-of-islands/</a> * </ul> * </p> * * @author YuCheng * */ public class LintCode0433NumIslandsTest { private final static Logger logger = LoggerFactory.getLogger(LintCode0433NumIslandsTest.class); /** * */ @Test public void testMain() { logger.debug("BEGIN"); // INIT GRID boolean[][] grid = { { true, true, false, false, false }, { false, true, false, false, true }, { false, false, false, true, true }, { false, false, false, false, false }, { false, false, false, false, true } }; // NULL CHECK if (grid.length == 0 || grid[0].length == 0) { System.out.println("NULL"); // return 0; } // GET SIZE int n = grid.length; int m = grid[0].length; // ARRAY FOR VISITED LOG boolean[][] visited = new boolean[n][m]; int count = 0; // LOOP FOR GRID for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] && !visited[i][j]) { numIslandsDFS(grid, visited, i, j); count++; } } } System.out.println(count); } /** * * @param grid * @param visited * @param x * @param y */ public void numIslandsDFS(boolean[][] grid, boolean[][] visited, int x, int y) { if (x < 0 || x >= grid.length) { return; } if (y < 0 || y >= grid[0].length) { return; } if (grid[x][y] != true || visited[x][y]) { return; } visited[x][y] = true; // Recursive call numIslandsDFS(grid, visited, x - 1, y); numIslandsDFS(grid, visited, x + 1, y); numIslandsDFS(grid, visited, x, y - 1); numIslandsDFS(grid, visited, x, y + 1); } }
点评
本质是求矩阵中连续区域的个数,很容易想到需要用深度优先搜索 DFS 来解,我们需要建立一个 visited 数组用来记录某个位置是否被访问过,对于一个为 true 且未被访问过的位置,我们递归进入其上下左右位置上为 true 的数,将其 visited 对应值赋为 true,继续进入其所有相连的邻位置,这样可以将这个连通区域所有的数找出来,并将其对应的 visited 中的值赋 true,找完次区域后,我们将结果 res 自增 1,然后我们在继续找下一个为 true 且未被访问过的位置,以此类推直至遍历完整个原数组即可得到最终结果。
这里需要有一个递归的调用。在递归调用之前需要进行判断是否超出边际,如果超出边际的话,就要跳出循环。
在一个节点进行遍历的时候,需要在递归调用的时候,同时针对这个节点搜索上下左右 4 个节点,如果找到需要了满足条件的 true,就继续查找,如果没有找到就退出。在这个过程的时候,需要将访问过的节点保存到访问控制的 2 维数组中。以便于在下次查找的时候跳过这个节点。
https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands
相关文章
- codeforce Number of Ways(暴力)
- 模型压缩-方案(一)-参数共享:ALBERT、BERT-of-Theseus
- ORA-12012: error on auto execute of job "SYS"."ORA$AT_OS_OPT_SY_363"
- 深度聚类算法研究综述(A Survey of Deep Clustering Algorithms)
- *17. Letter Combinations of a Phone Number
- TVCG A Comparison of Predictive Spatial Augmented Reality Cues for Procedural Tasks
- 解决Neither the JAVA_HOME nor the JRE_HOME environment variable is defined At least one of these...问题
- 强化学习在生成对抗网络文本生成中扮演的角色(Role of RL in Text Generation by GAN)(上)
- Premature optimization is the root of all evil.
- composer PHP Fatal error: Allowed memory size of 报错解决
- C. On Number of Decompositions into Multipliers -- Codeforces
- djoser - REST implementation of Django authentication system
- [LeetCode] 637. Average of Levels in Binary Tree 二叉树的层平均值
- Find minimum number of people to reach to spread a message across all people in twitter
- [LeetCode] 673. Number of Longest Increasing Subsequence 最长递增序列的个数