我的 C++ 程序停止工作

Question

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

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

提前这个code.Thanks有什么错误

Answer 1

你的算法有问题。你依赖

there is atmost one possible direction from any cell

而且这条路永远不可能是环形的。

在条件必然会失败的二进制矩阵的情况下。你从（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++。这使代码更易于阅读，您也很容易发现问题所在。

我的 C++ 程序停止工作

My c++ program has stopped working

c++

recursion

matrix

longest-path