算法问题的解决方案输出略有错误。怎么了？

Question

问题取自here

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

Sample 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],  
]  
Sample output:  
    [1, 2, 2, 2, 5]

我的解决方案：

我尝试递归地使用深度优先搜索来解决这个问题。

import java.util.*;
class River{
    int size;
    int[][]matrix;
    River(int[][]mat){
        matrix=mat;
    }
    void traverse(int x,int y){
        System.out.println(x+","+y);
        if((y-1)>=matrix.length && matrix[x][y-1]==1){
            size++;
            matrix[x][y-1]=0;
            traverse(x,y-1);
        } if((x+1)<matrix[0].length && matrix[x+1][y]==1){
            size++;
            matrix[x+1][y]=0;
            traverse(x+1,y);
        }if((x-1)>=matrix[0].length && matrix[x-1][y]==1){
                size++;
                matrix[x-1][y]=0;
                traverse(x-1,y);
        } 
        if((y+1)<matrix.length && matrix[x][y+1]==1){
            size++;
            matrix[x][y+1]=0;
            traverse(x,y+1);
        }
    }
}
class Program {
  public static List<Integer> riverSizes(int[][] matrix) {
        List<Integer> SList = new ArrayList<>();
        List<River> RList = new ArrayList<>();
        System.out.println("Traversal:");

        for(int i=0;i<matrix[0].length;i++){
            for(int j=0;j<matrix.length;j++){
                if(matrix[i][j]==1){
                    matrix[i][j]=0;
                    River river = new River(matrix);
                    river.size++;
                    river.traverse(i,j);
                    RList.add(river);
                }
            }
        }
        System.out.println("Sizes:");
        for(River r:RList){
            SList.add(r.size);
            System.out.println(r.size);
        }
    return SList;
    }
    public static void main(String[]args){
        int[][]riverM={
        {1,0,0,0,0,0,1},
        {0,1,0,0,0,1,0},
        {0,0,1,0,1,0,0},
        {0,0,1,1,1,0,0},
        {0,0,1,0,1,0,0},
        {0,1,0,0,0,1,0},
        {1,0,0,0,0,0,1},
    };

        System.out.println("("+riverM.length+","+riverM[0].length+")");
        riverSizes(riverM);
    }
}

我的输出通过了 7/12 个案例。这是其中一个出错的案例。

我的输出：

Sizes:
1,1,1,1,6,1,1,1,1,1,

预期输出：

Sizes:
1,1,1,1,7,1,1,1,1,1,

谁能告诉我出了什么问题？

Answer 1

我认为问题出在您的 traverse 函数中：

if((y-1)>=matrix.length && matrix[x][y-1]==1){...}

条件(y-1)>=matrix.length的左边部分是错误的。在这里，如果我错了，请纠正我，你只是想防止IndexOutOfBoundsException。为此，您应该测试类似 (y-1) >= 0.

的内容

测试 x 索引时出现同样的错误。使用这些修复程序测试输出，没有检查是否还有其他问题。

算法问题的解决方案输出略有错误。怎么了？

Solution to algorithm problem has slightly incorrect output. What's wrong?

java

algorithm

depth-first-search