Я попытался найти самый длинный путь в матрице с последовательными цифрами, который дает правильный ответ. Вызов функции выполняется рекурсивно, пока рядом нет последовательных цифр, и он проверяет каждый раз, посещается ли ячейка или нет
#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;
}
в чем ошибка в этом коде. Заранее спасибо
У вашего алгоритма есть проблема. Вы полагаетесь на то, что
Существует как минимум одно возможное направление от любой ячейки
и что этот путь никогда не может быть круговым.
В случае бинарной матрицы эти условия обречены на неудачу.
Вы переходите от (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) и т. Д. -)
Таким образом, ваш алгоритм завершается, когда стек заполнен, так как с предусловиями, которые вы выбрали, наибольшая длина пути бесконечна, и только Чак Норрис может делать бесконечные циклы за конечное время.
Изменить: я решительно поддерживаю комментарий Xeverous. Вы действительно должны реорганизовать свой код, чтобы быть более с ++. Это облегчает чтение кода, и вы легко заметите проблему.
Других решений пока нет …