遞歸 - 找到矩陣中最大的蠕蟲

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

Answer 2

你的程序工作正常。 加入此項。

public static int longestWarm(int[][] arr) { 
    int len = arr.length; 
    int max = 0; 
    for (int row = 0; row < len; ++row) { 
     for (int col = 0; col < len; ++col) { 
      int length = longestWarm(arr, row, col); 
      if (length > max) 
       max = length; 
     } 
    } 
    return max; 
} 

並嘗試這個

int[][] arr = { 
    {3, 4, 5, 6}, 
    {5, 6, 2, 7}, 
    {12, 13, 14, 15}, 
    {19, 18, 17, 16}}; 
System.out.println("lngest warm=" + longestWarm(arr));