0

So the problem is given a 2D matrix of non-negative integers, we have to find the minimum sum path from top-left cell to the bottom-right cell. The directions in which we can move is left, right, top, and bottom.

Say the matrix is: Please Click here for image of the matrix

Now the numbers in green are the ones which are included in the minimum sum path. The answer comes to be 327. I got the correct answer using djikstra's algorithm O(n^2) complexity. Out of curiosity, I tried solving it using backtracking. Used a visited matrix to keep track and brute-forcing all the way. I know that it is a poor approach but it should at least give correct answer. But the answer which I get from this approach is 426.

Can anyone tell me why is this approach giving wrong answer?

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

As I said above, I am somehow receiving the incorrect answer. 426 instead of 327. Can someone tell me why is it so?

Thanks!

Sank_BE
  • 33
  • 5
  • 2
    [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). -- *I know that it is a poor approach but it should at least give correct answer* -- Why do you say that? A program doesn't have a mind of its own. You need to debug your code and not assume that you have produced a program with flawless logic and it's the compiler's fault your program doesn't work. – PaulMcKenzie Jul 07 '19 at 19:47
  • 1
    https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h –  Jul 07 '19 at 20:02
  • Okay I solved this question by taking a smaller example and debugging right now. It appears that my destination cell was visited once and never again. visit[x][y]=true; should have been below the end condition. I have been debugging this for sometime (hours) before I posted here. Sorry for inconvenience. Thanks. – Sank_BE Jul 07 '19 at 20:05

1 Answers1

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

The above code is the correct code. We need to avoid marking the destination as visited true all the time. If we do, we will have to accept the first possibility we get as the answer which may or may not be correct.

Sank_BE
  • 33
  • 5
  • “The above code is the correct code.” — **No.** As explained in the thread linked in Neil’s comment above, you mustn’t use `#include `. – Konrad Rudolph Jul 07 '19 at 20:54
  • Correct code as in logic of the program. I understand that the #include is a bad practice for programming, but in exams as a student we can use STL and this imports everything. So it is a necessary evil for us. I agree that in long practice we should avoid this line. – Sank_BE Jul 09 '19 at 01:20