java - 算法问题的解决方案输出略有不正确。怎么了？

Question

问题取自here

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

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 索引时出现同样的错误。使用这些修复测试输出，没有检查是否还有其他错误。