Таким образом, задача дана двумерная матрица неотрицательных целых чисел, мы должны найти путь минимальной суммы от верхней левой ячейки до нижней правой ячейки.Направления, в которых мы можем двигаться, это левый, правый, верхний и нижний.
Скажите, что матрица: Пожалуйста, нажмите здесь для изображения матрицы
Теперьчисла в зеленом - это те, которые включены в путь минимальной суммы.Ответ будет 327. Я получил правильный ответ, используя алгоритм Джикстра O (n ^ 2) сложности.Из любопытства я попытался решить эту проблему с помощью возврата.Использовал посещаемую матрицу для отслеживания и грубого принуждения.Я знаю, что это плохой подход, но он должен по крайней мере дать правильный ответ.Но ответ, который я получаю от этого подхода, - 426.
Может кто-нибудь сказать мне, почему этот подход дает неправильный ответ?
#include<bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
int c=0;
int shortest_c = INT_MAX;
bool isSafe(int x,int y,int grid[ROW][COL],bool visit[ROW][COL])
{
if(x<0 || x>=ROW || y<0 || y>=COL || visit[x][y]==true)
return false;
return true;
}
void shortest(int grid[ROW][COL],int x,int y,int val, bool visit[ROW][COL])
{
if(isSafe(x,y,grid,visit))
{
visit[x][y]=true;
val+=grid[x][y];
if(x==ROW-1 && y==COL-1)
{
shortest_c = min(shortest_c,val);
return;
}
shortest(grid,x,y-1,val,visit);
shortest(grid,x,y+1,val,visit);
shortest(grid,x-1,y,val,visit);
shortest(grid,x+1,y,val,visit);
visit[x][y]=false;
}
return;
}
int main()
{
int grid[ROW][COL] =
{
{31, 100, 65, 12, 18},
{10, 13, 47, 157, 6},
{100, 113, 174, 11, 33},
{88, 124, 41, 20, 140},
{99, 32, 111, 41, 20}
};
bool visit[ROW][COL];
for(int i=0;i<ROW;++i)
{
for(int j=0;j<COL;++j)
{
visit[i][j]=false;
}
}
cout<<sum<<endl;
shortest(grid,0,0,0,visit );
cout<<shortest_c<<endl;
return 0;
}
Как я сказал выше, я каким-то образом получаю неправильныйответ.426 вместо 327. Может кто-нибудь сказать мне, почему это так?
Спасибо!