一个长宽为row,column的int型二维数组,每个位置的值有0或1随机组成,请用java代码输出其存在的由数字1组成的连接块个数。二维数组中,当一数字的上下左右存在至少另一个相同大小的数字时,则这两数字称为连着,多个连着的相同大小的数字组成的区域称为连接块
时间: 2023-06-14 12:05:54 浏览: 50
可以深度优先搜索(DFS)或广度优先搜索(BFS)来解决这个问题。以下是使用DFS的Java代码:
```java
public static int countIslands(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private static void dfs(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
return;
}
grid[i][j] = 2;
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
```
这个算法遍历整个二维数组。对于每个值为1的位置,我们从该位置开始进行DFS。在DFS期间,我们将与当前位置相邻且值为1的位置标记为2,以避免重复计算。每次找到一个新的1时,我们增加计数器并继续进行DFS,直到我们遍历了整个连接块。
示例输入:
```
int[][] grid = {
{1, 1, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 1, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
};
```
输出:3 (有3个连接块)
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)