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

Question

我有以下问题:对于 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。请帮助找出我做错了什么。

Answer 1

我使用 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));
        }
    }
}