一个长宽为row,column的int型二维数组,每个位置的值有0或1随机组成,请用java代码输出其存在的由数字1组成的连接块个数。 二维数组中,当一数字的上或下或左或右等于另一个相同大小的数字时,则这两数字称为连着,多个连着的相同大小的数字组成的区域称为一个连接块, 当一数字和其上下左右的值均不相同时,该数字组成的这一位置也叫连接块。
时间: 2023-06-16 21:03:06 浏览: 71
以下是Java代码实现:
```
public class ConnectionBlocks {
public int countConnectionBlocks(int[][] arr) {
int count = 0;
boolean[][] visited = new boolean[arr.length][arr[0].length];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] == 1 && !visited[i][j]) {
dfs(arr, visited, i, j);
count++;
}
}
}
return count;
}
private void dfs(int[][] arr, boolean[][] visited, int i, int j) {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
visited[i][j] = true;
for (int[] dir : dirs) {
int newRow = i + dir[0];
int newCol = j + dir[1];
if (newRow >= 0 && newRow < arr.length && newCol >= 0 && newCol < arr[0].length
&& arr[newRow][newCol] == 1 && !visited[newRow][newCol]) {
dfs(arr, visited, newRow, newCol);
}
}
}
}
```
代码中使用了深度优先搜索(DFS)算法来遍历连通块,使用一个布尔类型的二维数组visited来记录已经访问过的位置,避免对同一位置重复访问。对于每一个值为1且未被访问过的位置,都进行一次DFS搜索,并且将计数器count加1,最后返回count即可。
阅读全文