Почему решение о возврате не дает правильного ответа? - PullRequest
0 голосов
/ 07 июля 2019

Таким образом, задача дана двумерная матрица неотрицательных целых чисел, мы должны найти путь минимальной суммы от верхней левой ячейки до нижней правой ячейки.Направления, в которых мы можем двигаться, это левый, правый, верхний и нижний.

Скажите, что матрица: Пожалуйста, нажмите здесь для изображения матрицы

Теперьчисла в зеленом - это те, которые включены в путь минимальной суммы.Ответ будет 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. Может кто-нибудь сказать мне, почему это так?

Спасибо!

1 Ответ

0 голосов
/ 07 июля 2019
#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))
    {



        val+=grid[x][y];

        if(x==ROW-1 && y==COL-1)
        {
            shortest_c = min(shortest_c,val);
            return;

        }
        visit[x][y]=true;

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

Приведенный выше код является правильным кодом. Мы должны избегать маркировки места назначения как посещенного истинно все время. Если мы это сделаем, нам придется принять первую возможность, которую мы получим в качестве ответа, которая может быть или не быть правильной.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...