-4

我试图在具有连续数字的矩阵中找到最长的路径，从而给出正确的答案。函数调用递归执行，直到附近没有连续的数字，并且每次检查单元格是否被访问

#include<bits/stdc++.h>
#define n 3
using namespace std;

// Returns length of the longest path beginning with mat[i][j].
// This function mainly uses lookup table dp[n][n]
int findLongestFromACell(int i, int j, int mat[n][n], int dp[n][n])
{
    // Base case
    if (i<0 || i>=n || j<0 || j>=n)
        return 0;

    // If this subproblem is already solved
    if (dp[i][j] != -1)
        return dp[i][j];

    // Since all numbers are unique and in range from 1 to n*n,
    // there is atmost one possible direction from any cell
    if (j<n-1 && ((mat[i][j] +1) == mat[i][j+1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j+1,mat,dp);

    if (j>0 && (mat[i][j] +1 == mat[i][j-1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j-1,mat,dp);

    if (i>0 && (mat[i][j] +1 == mat[i-1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i-1,j,mat,dp);

    if (i<n-1 && (mat[i][j] +1 == mat[i+1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i+1,j,mat,dp);

    // If none of the adjacent fours is one greater
    return dp[i][j] = 1;
}

// Returns length of the longest path beginning with any cell
int finLongestOverAll(int mat[n][n])
{
    int result = 1;  // Initialize result

    // Create a lookup table and fill all entries in it as -1
    int dp[n][n];
    memset(dp, -1, sizeof dp);

    // Compute longest path beginning from all cells
    for (int i=0; i<n; i++)
    {
      for (int j=0; j<n; j++)
       {
          if (dp[i][j] == -1)
             findLongestFromACell(i, j, mat, dp);

          //  Update result if needed
          result = max(result, dp[i][j]);
       }
     }

     return result;
}

// Driver program
int main()
{
   int  mat[n][n] = {{1, 10, 9},
                    {5, 3, 8},
                    {4, 6, 7}};
   cout << "Length of the longest path is "
        << finLongestOverAll(mat);
   return 0;
}

但是当我尝试相同的代码来查找二进制矩阵中的最长路径时，程序停止执行

#include<bits/stdc++.h>
#define n 3
using namespace std;

// Returns length of the longest path beginning with mat[i][j].
// This function mainly uses lookup table dp[n][n]
int findLongestFromACell(int i, int j, int mat[n][n], int dp[n][n])
{
    // Base case
    if (i<0 || i>=n || j<0 || j>=n)
        return 0;

    // If this subproblem is already solved
    if (dp[i][j] != -1)
        return dp[i][j];

    // Since all numbers are unique and in range from 1 to n*n,
    // there is atmost one possible direction from any cell
    if (j<n-1 && (1 == mat[i][j+1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j+1,mat,dp);

    if (j>0 && (1 == mat[i][j-1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j-1,mat,dp);

    if (i>0 && (1 == mat[i-1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i-1,j,mat,dp);

    if (i<n-1 && (1 == mat[i+1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i+1,j,mat,dp);

    // If none of the adjacent fours is one greater
    return dp[i][j] = 1;
}

// Returns length of the longest path beginning with any cell
int finLongestOverAll(int mat[n][n])
{
    int result = 1;  // Initialize result

    // Create a lookup table and fill all entries in it as -1
    int dp[n][n];
    memset(dp, -1, sizeof dp);

    // Compute longest path beginning from all cells
    for (int i=0; i<n; i++)
    {
      for (int j=0; j<n; j++)
       {
          if (dp[i][j] == -1)
             findLongestFromACell(i, j, mat, dp);

          //  Update result if needed
          result = max(result, dp[i][j]);
       }
     }

     return result;
}

// Driver program
int main()
{
   int  mat[n][n] = {{1, 0, 0},
                    {1, 0, 0},
                    {1, 1, 1}};
   cout << "Length of the longest path is "
        << finLongestOverAll(mat);
   return 0;
}

这段代码有什么错误。在此先感谢

4

1 回答 1

0

你的算法有问题。你依赖于这样一个事实

任何单元格至多有一个可能的方向

并且那条路永远不可能是圆形的。

在二进制矩阵的情况下，条件必然会失败。您从 (0,0) 到 (1,0) 到 (0,0) 到 (1,0) 到 (0,0) 到 (1,0) 到 (0,0) 到 (1,0)到 (0,0) 到 (1,0) 到 (0,0) 到 (1,0) 到 (0,0) 到 (1,0) 到 (0,0) 到 (1,0) 到 ( 0,0) 到 (1,0) 到 (0,0) 到 (1,0) 到 (0,0) 到 (1,0) 到 (0,0) 到 (1,0) 等等： -)

因此，您的算法在堆栈已满时终止，因为在您选择的最长路径长度是无限的前提条件下，只有 Chuck Norris 可以在有限时间内进行无限循环。

编辑：我强烈支持 Xeverous 的评论。你真的应该将你的代码重构为更多的 C++。这使代码更易于阅读，并且您很容易看到问题所在。

于 2017-09-19T13:55:03.650 回答