java - 使用深度优先遍历矩阵

Question

问题

给定一个二维数组(矩阵)，其高度和宽度可能不相等，仅包含 0 和 1。每个0代表土地，每个1代表河流的一部分。一条河流由任意数量的水平或垂直相邻(但不是对角线相邻)的 1 组成。形成河流的相邻 1 的数量决定了它的大小。编写一个函数，返回一个数组，该数组包含输入矩阵中表示的所有河流的大小。请注意，这些尺寸不需要按任何特定顺序排列。

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]

我的方法

在评估问题之后，我觉得这应该使用类似算法的图形遍历来完成，也许是深度优先搜索。所以这正是我所做的。

我从左上角遍历矩阵，看看是否访问了该值，如果未访问，如果值为 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);
    }
}

Answer 1

you are given a two-dimensional array (matrix) of potentially unequal height and width 

但是您正在对高度和宽度始终相同的矩阵进行操作

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);
}