Mein C++ - Programm funktioniert nicht

Question

Ich habe versucht, den längsten Weg in einer Matrix mit aufeinanderfolgenden Ziffern zu finden, die richtige Antwort gibt.Der Funktionsaufruf wird rekursiv ausgeführt, bis keine aufeinanderfolgenden Ziffern in der Nähe sind und es prüft jedes Mal, ob die Zelle besucht wird oder nicht

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

Aber wenn ich den gleichen Code versucht, stoppt das Programm den längsten Weg in einer binären Matrix zu finden

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

Ausführung, was der Fehler in diesem code.Thanks im Voraus

Answer 1

Ihr Algorithmus hat ein Problem. Sie beruhen auf der Tatsache, dass

dort atmost eine mögliche Richtung von jeder Zelle ist

und dass dieser Weg nicht kreisförmig sein kann.

Im Falle einer binären Matrix müssen Bedingungen nicht erfüllt werden. Sie bewegen sich von (0,0) zu (1,0) zu (0,0) zu (1,0) zu (0,0) zu (1,0) zu (0,0) zu (1,0) bis (0,0) bis (1,0) bis (0,0) bis (1,0) bis (0,0) bis (1,0) bis (0,0) bis (1,0) bis (0,0) bis (1,0) bis (0,0) bis (1,0) bis (0,0) bis (1,0) bis (0,0) bis (1,0) so weiter :-)

So endet Ihr Algorithmus, wenn der Stack voll ist, denn mit den von Ihnen gewählten Voraussetzungen ist die längste Pfadlänge unendlich und nur Chuck Norris kann unendliche Schleifen in endlicher Zeit ausführen.

Edit: Ich unterstütze stark den Kommentar von Xeverous. Du solltest deinen Code wirklich umgestalten, um mehr C++ zu sein. Das macht den Code leichter lesbar und Sie hätten das Problem leicht erkannt.