java - 递归-在矩阵中找到最大的蠕虫

我有以下问题：
对于nXn矩阵，我们将定义一个大小为k的“蠕虫”，它是一系列具有连续数字的相邻单元格。相邻单元格是当前单元格的右\左\上\下的单元格（不是对角线）。
我需要编写一个递归函数，该函数返回数组中最长的蠕虫
例如：在矩阵中：

{{3,4,5,6},
 {5,6,2,7},
 {12,13,14,15},
 {19,18,17,16}};

最长的蠕虫是8个细胞。从[2] [0]开始，到[3] [0]结束。

到目前为止，我已经编写了以下代码：

public static int longestWarm(int[][] arr, int row, int col) {
    if (row < 0 || row >= arr.length || col < 0 || col >= arr.length) return 0;
    if (col >= arr.length || row >= arr.length) return 0;

    int sum1 = 1, sum2 = 1, sum3 = 1, sum4 = 1;

    if (row > 0 && arr[row][col] == arr[row - 1][col] - 1)
            sum1 = 1 + longestWarm(arr, row - 1,col);
    else if (row < arr[0].length - 1 && arr[row][col] == arr[row + 1][col] - 1)
            sum2 = 1 + longestWarm(arr, row + 1, col);
    else if (col > 0 && arr[row][col] == arr[row][col - 1] - 1)
            sum3 = 1 + longestWarm(arr, row, col - 1);
    else if (col < arr[0].length - 1 && arr[row][col] == arr[row][col + 1] - 1)
            sum4 = 1 + longestWarm(arr, row, col + 1);

    int max1 = Math.max(sum1, sum2);
    int max2 = Math.max(sum3, sum4);

    return Math.max(max1, max2);
}

问题是我得到了我在矩阵中找到的第一个蠕虫，而不是最大的蠕虫。我的输出是5，而不是8。
请帮助找到我在做什么错。

最佳答案

我使用了is_tail方法，只修剪从相邻单元格不小于1的单元格开始的蠕虫。如果存在这样的邻居，则显然不是最长蠕虫的尾巴。在每条尾巴上，您都可以找到与该细胞相似的最大蠕虫。

import java.util.ArrayList;

//a pair of ints, row and col, that indicate a cell in a matrix
class Cell {
    int row;
    int col;

    public Cell(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public int get_row() {
        return row;
    }

    public int get_col() {
        return col;
    }

    public String toString() {
        return "row: " + row + " col: " + col;
    }
}

// a class to hold the matrix data and methods
// so that every call doesnt require passing the pointer m
class Matrix {
    // m used for the matrix so that i dont have to type matrix repeatedly
    int[][] m;
    int height;
    int width;

    public Matrix(int[][] m) {
        this.m = m;
        height = m.length;
        width = m[0].length;
    }

    public int get_height() {
        return height;
    }

    public int get_width() {
        return width;
    }

    // checks if the cell at row,col is a tail
    // a tail is a cell with 0 neighbors that are 1 less than its value
    public boolean is_tail(int row, int col) {
        if (row < 0 || row >= m.length || col < 0 || col >= m[0].length)
            return false;

        int curVal = m[row][col]; // Value in the cell being checked

        // check if neighbor is out of bounds, then if it is smaller
        if (row - 1 >= 0 && m[row - 1][col] == curVal - 1)
            return false;
        if (row + 1 < m.length && m[row + 1][col] == curVal - 1)
            return false;
        if (col - 1 >= 0 && m[row][col - 1] == curVal - 1)
            return false;
        if (col + 1 < m[0].length && m[row][col + 1] == curVal - 1)
            return false;

        return true;
    }

    public ArrayList<Cell> longestWorm(int row, int col) {
        if (row < 0 || row >= m.length || col < 0 || col >= m[0].length)
            return new ArrayList<Cell>();

        int curVal = m[row][col];
        ArrayList<Cell> longest_path = new ArrayList<Cell>();

        if (row - 1 >= 0 && m[row - 1][col] == curVal + 1) {
            ArrayList<Cell> path_left = longestWorm(row - 1, col);
            if (path_left.size() > longest_path.size())
                longest_path = path_left;
        }

        if (row + 1 < m.length && m[row + 1][col] == curVal + 1) {
            ArrayList<Cell> path_right = longestWorm(row + 1, col);
            if (path_right.size() > longest_path.size())
                longest_path = path_right;
        }

        if (col - 1 >= 0 && m[row][col - 1] == curVal + 1) {
            ArrayList<Cell> path_up = longestWorm(row, col - 1);
            if (path_up.size() > longest_path.size())
                longest_path = path_up;
        }

        if (col + 1 < m[0].length && m[row][col + 1] == curVal + 1) {
            ArrayList<Cell> path_down = longestWorm(row, col + 1);
            if (path_down.size() > longest_path.size())
                longest_path = path_down;
        }

        longest_path.add(new Cell(row, col));
        return longest_path;
    }
}

class Main {

    public static void main(String[] args) {
        int[][] matrix = { { 3, 4, 5, 6 }, { 5, 6, 2, 7 }, { 12, 13, 14, 15 }, { 19, 18, 17, 16 } };

        ArrayList<Cell> longest_worm = new ArrayList<Cell>();

        Matrix myMatrix = new Matrix(matrix);
        for (int i = 0; i < myMatrix.get_height(); i++) {
            for (int j = 0; j < myMatrix.get_width(); j++) {
                if (myMatrix.is_tail(i, j)) {
                    ArrayList<Cell> new_worm = myMatrix.longestWorm(i, j);
                    if (new_worm.size() > longest_worm.size()) {
                        longest_worm = new_worm;
                    }
                }
            }
        }

        for (int i = longest_worm.size() - 1; i >= 0; i--) {
            System.out.println(longest_worm.get(i));
        }
    }
}

关于java - 递归-在矩阵中找到最大的蠕虫，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44959439/