-1

I am trying to solve the backtracking problem rat in a maze, but it's not printing the solution, Please look into code and help me out.

The code is below:

#include <bits/stdc++.h>
using namespace std;

vector<string> ans;

bool isSafe(vector<vector<int>> &matrix, vector<vector<int>> &visited, int size, int srcx, int srcy)
{
    if (srcx >= 0 && srcy >= 0 && srcy < size && srcx < size && matrix[srcx][srcy] == 1 && !visited[srcx][srcy])
    {
        return true;
    }
    else
    {
        return false;
    }
}

void findPathUtiltity(vector<vector<int>> &matrix, vector<vector<int>> &visited, int size, int srcx, int srcy, string temp)
{
    // check if we are at (3,3)
    if (srcx == size - 1 && srcy == size - 1)
    {
        ans.push_back(temp);
        return;
    }
    // mark visited as true
    visited[srcx][srcy] = 1;
    // DOWN
    if (isSafe(matrix, visited, srcx + 1, srcy, size))
    {
        findPathUtiltity(matrix, visited, size, srcx + 1, srcy, temp + "D");
    }
    // LEFT
    if (isSafe(matrix, visited, srcx, srcy - 1, size))
    {
        findPathUtiltity(matrix, visited, size, srcx, srcy - 1, temp + "L");
    }
    // Right
    if (isSafe(matrix, visited, srcx, srcy + 1, size))
    {
        findPathUtiltity(matrix, visited, size, srcx, srcy + 1, temp + "R");
        // UP
        if (isSafe(matrix, visited, srcx - 1, srcy, size))
        {
            findPathUtiltity(matrix, visited, size, srcx - 1, srcy, temp + "U");
        }
    }
    // mark all 0 to backtrack and check all other path
    visited[srcx][srcy] = 0;
    return;
}

vector<string> findPath(vector<vector<int>> &matrix, int size)
{
    if (matrix[0][0] == 0)
    {
        return ans;
    }

    vector<vector<int>> visited(size, vector<int>(size, 0));
    findPathUtiltity(matrix, visited, size, 0, 0, "");
    return ans;
}

int main()
{

    vector<vector<int>> matrix = {
        {1, 0, 0, 0, 0},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 0, 1},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0, 1}};
    vector<string> path = findPath(matrix, matrix.size());

    for (int i = 0; i < path.size(); i++)
    {
        cout << path[i] << " ";
    }

    return 0;
}

I am trying to solve the backtracking problem rat in a maze, but it's not printing the solution, i taken matrix of vector<vector<int>>matrix; . I try to DRY run there i'm getting correct output. Please look into code and help me out.

Dwarikanath
  • 11
  • 2
  • 3
    `srcy < size - 1 && srcx <= size - 1` This looks suspicious. – 273K Mar 30 '23 at 18:33
  • 1
    Side note: Try to minimize what you include in a program to reduce the odds of colliding with a with an identifier you might not even know exists. That means don't use `#include ` and pull in the entire C++ Standard Library and its tens of thousands of declarations and definitions. Definitely don't pull them into the global namespace with `using namespace std;` because that's just asking the compiler to make you pay for being lazy. – user4581301 Mar 30 '23 at 18:36
  • 2
    Whatever's going wrong isn't being picked up by the usual suspects: https://godbolt.org/z/Pa1hr9o4h What happens when you step through the code with a debugger? Where does the program start to deviate from your expectations? The sooner you can spot unexpected behaviour, like the wrong value being stored or the wrong path taken, the closer you are to spotting the actual bug. – user4581301 Mar 30 '23 at 18:41
  • Side note: the `dsa` tag is for questions about the Digital Signature Algorithm, a fun bit of crypto, and not for questions about Data Structures and Algorithms. Always give a new tag's tag info a quick read-over before you use it. The better categorized a question is, the better the pool of eyes looking at it and the easier it is to find for future askers with a similar problem. – user4581301 Mar 30 '23 at 18:43
  • 1
    `srcy < size - 1 && srcx <= size - 1` should be `srcy < size && srcx < size`. Arrays and vector indexes start at zero. This fact causes newbies to produce all sort of strange ways of checking vector bounds but simply `i >= 0 && i < size` is the easy and correct way to do it. – john Mar 30 '23 at 18:46
  • 1
    *Please look into code and help me out* -- Once you decide to write a program, the debugging of the program if it goes wrong falls on your shoulders, no one else. At the very least, you should be able to identify *where* the code goes wrong and explain where it goes wrong *to us*. We are not asking you to fix the issue, that is a different story, but you must know where the program goes wrong, since you wrote the code yourself (unless if you copied it from somewhere). – PaulMcKenzie Mar 30 '23 at 18:47
  • 1
    You definitely lost me to look further into your code at this line: [`#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h?r=Saves_AllUserSaves). That's simply wrong, period. – πάντα ῥεῖ Mar 30 '23 at 19:03
  • 1
    The order of the `isSafe` parameters does not correspond to the order of the arguments you provide in the calls of that function. So none of the neighbors is considered safe, and no path is inspected. All this can be easily detected with step by step debugging. – trincot Mar 30 '23 at 19:07
  • There is no point to passing the size as an argument - it just adds a bug opportunity (as you've noticed by now). Use `matrix.size()` instead. – molbdnilo Mar 31 '23 at 07:33

1 Answers1

1

There are several issues; all related to the isSafe function:

  • The test for the y-coordinate is too strict and will never allow the path to reach the bottom-right corner of the maze. Instead of srcy < size - 1 you should have srcy < size. There is no good reason why you would perform the conditions differently for x and y coordinate. So align the srcx condition to this pattern.

  • In the function header, the size parameter comes before the srcx and srcy parameters, but in the function calls you pass size as the last argument.

  • The if (<boolean expr>) return true; else return false; construct is adding a layer of execution that is unnecessary. Just return the boolean expression.

Here is the correction:

bool isSafe(vector<vector<int>> &matrix, vector<vector<int>> &visited, 
            int srcx, int srcy, int size)
{
    return srcx >= 0 && srcy >= 0 && srcy < size && srcx < size 
                     && matrix[srcx][srcy] == 1 && !visited[srcx][srcy];
}
trincot
  • 317,000
  • 35
  • 244
  • 286