首先使用深度遍历矩阵。
首先使用深度遍历矩阵。
提问于 2019-08-27 21:58:44
问题
您将得到一个高度和宽度可能不等的二维数组(矩阵)，该数组仅包含0和1s。每个0代表土地，每个1代表河流的一部分。河流由水平或垂直相邻(但不是对角线相邻)的任意数量的1s组成。形成一条河流的相邻1s的数量决定了它的大小。编写一个函数，返回输入矩阵中表示的所有河流大小的数组。请注意，这些大小不需要以任何特定的顺序。
Input
[
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]
Output [1,2,2,2,5]My Approach
在对问题进行评估后，我觉得应该使用图遍历，比如算法，可能是深度优先搜索。所以我就是这么做的。
我从左上角遍历矩阵，看看是否访问了值，如果没有访问，如果值为1，则遍历所有节点，并保持一个计数器以保持河流的大小。最后，我用总河流大小更新了一个数组列表。
由于某些原因，我的结果是不正确的，我不知道我做错了什么。我也用手追踪我的代码，但找不出问题。
我的代码
import java.util.ArrayList;
class Program {
public static ArrayList<Integer> riverSizes(int[][] matrix) {
ArrayList<Integer> result = new ArrayList<Integer>();
boolean [][] visitStatus = new boolean [matrix.length][matrix[0].length];
for(int row = 0; row<matrix.length; row++){
for(int col = 0; col<matrix.length; col++){
int count = 0;
count = traverseMatrix(row,col,matrix,visitStatus,count);
result.add(count);
}
}
return result;
}
public static int traverseMatrix(int row, int col, int [][] matrix, boolean [][] visitStatus, int count){
if(visitStatus[row][col] == true){
return count;
}else if(matrix[row][col] == 0){
visitStatus[row][col] = true;
return count;
}else{
count++;
visitStatus[row][col] = true;
if(isValid(row,col-1,matrix)){
return traverseMatrix(row,col-1,matrix,visitStatus,count);
}
if(isValid(row,col+1,matrix)){
return traverseMatrix(row,col+1,matrix,visitStatus,count);
}
if(isValid(row-1,col,matrix)){
return traverseMatrix(row-1,col,matrix,visitStatus,count);
}
if(isValid(row+1,col,matrix)){
return traverseMatrix(row+1,col,matrix,visitStatus,count);
}
}
return count;
}
public static boolean isValid(int row, int col,int[][] matrix){
return (row >= 0 && row < matrix.length) && (col >= 0 && col < matrix[0].length);
}
}回答 4
Stack Overflow用户
回答已采纳
发布于 2019-08-27 22:35:37
将count转换为局部变量并累积它：
static int traverseMatrix(int row, int col, int[][] matrix, boolean[][] visitStatus) {
if (visitStatus[row][col] || matrix[row][col] == 0) {
return 0;
}
visitStatus[row][col] = true;
int count = 1;
if (isValid(row, col - 1, matrix)) {
count += traverseMatrix(row, col - 1, matrix, visitStatus);
}
...
return count;
}Stack Overflow用户
发布于 2019-08-28 04:40:50
给出了一个高度和宽度不相等的二维数组(矩阵)。
但是，在高度和宽度上，总是对相同大小的矩阵执行操作。
for(int row = 0; row<matrix.length; row++){
for(int col = 0; col<matrix.length; col++){ .. }}你应该像下面这样使用维数，其余的东西我想都足够好了。
for(int row = 0; row<matrix.length; row++){
for(int col = 0; col<matrix[row].length; col++){ .. }}而这些变化也需要应用于函数“isValid”中。
public static boolean isValid(int row, int col,int[][] matrix){
return (row >= 0 && row < matrix.length) && (col >= 0 && col < matrix[row].length);
}Stack Overflow用户
发布于 2019-08-27 22:47:00
除了@OleksandrPyrohov的回答之外，还要检查在调用traverseMatrix之前是否已经访问了当前单元：
public static ArrayList<Integer> riverSizes(int[][] matrix) {
ArrayList<Integer> result = new ArrayList<Integer>();
boolean [][] visitStatus = new boolean [matrix.length][matrix[0].length];
for(int row = 0; row<matrix.length; row++){
for(int col = 0; col<matrix.length; col++){
if ( !visitStatus[row][col] ) {
int count = 0;
count = traverseMatrix(row,col,matrix,visitStatus,count);
result.add(count);
}
}
}
return result;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/57682750
复制相关文章
相似问题
腾讯云开发者
