Can't find why the code is going into infinite loop

Debugging Help
#1

Problem Info

Grid Paths

My Work

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (3.141592653589)
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

int ans;
string s;
vector<int> dir = {1, 0, -1, 0, 1}; // D,L,U,R
string dic = "DLUR";

void paths(int i, int j, vector<vector<int>> vis, int cnt)
{
    // if it reaces the desired block, stop (increment ans if all blocks covered)
    if (i == 6 && j == 0)
    {
        if (cnt == 48)
            ans++;
        return;
    }

    // if it can only go either left or right stop
    if ((i > 0 && i < 6 && vis[i + 1][j] && vis[i - 1][j]) || (i == 6 && vis[i - 1][j]) || (i == 0 && vis[i + 1][j]))
        return;


    // try for each of four direction
    for (int k = 0; k < 4; k++)
    {
        int ii = i + dir[k], jj = j + dir[k + 1];

        //only go in that direction if it is in bounds, not visited and the move matches our pattern
        if (ii >= 0 && ii < 7 && jj >= 0 && jj < 7 && vis[ii][jj] == 0 && (s[cnt] == '?' || dic[k] == s[cnt]))
        {
            vis[ii][jj] = 1;

            paths(ii, jj, vis, cnt + 1);

            vis[ii][jj] = 0;
        }
    }
}

int main()
{
    fast;

    cin >> s;

    //2d array to keep track of visited blocks
    vector<vector<int>> vis(7, vector<int>(7, 0));

    ans = 0;

    vis[0][0] = 1;

    paths(0, 0, vis, 0);

    cout << ans;

    return 0;
}

Add explanation of code here

What I’ve Tried

I looked through carefully but can’t figure out why it is going into infinte loop( i assume).
When I compile it and run the program, it runs for 8 seconds and gives 0 output. And when I run it on CPH vscode extension, it again runs for 8 seconds, and gives output SIGTERM.

Question

What is wrong with this code?
Thanks for the help.

Checklist

See How to ask for help on a problem for more information.

  • Include a link to the problem
  • Format your post (especially code blocks)
  • Include what you’ve tried so far
  • Add comments to your code
  • Read the debugging module
#2

What’s this?

Do you mean it doesn’t output anything, or it outputs 0? When I run the code, it outputs 0 (link).

#3

Yes it outputs 0 (when compiled using g++ and run). But I can’t figure out why.

Also, CPH is just a VS Code extension that allows to run test cases for a program. When I run the program using this, I get SIGTERM as output

#4

just found one bug, it might be better to pass the vis array as reference here :

void paths(int i, int j, vector<vector<int>> &vis, int cnt)

But still the output is 0

#5

Managed to make it work.
The main problem was with the line where I stopped the search when I could only go left or right.

Correct code :

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (3.141592653589)
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

string s;
int ans;

int dir[] = {1, 0, -1, 0, 1};
string dic = "DLUR";

void paths(int i, int j, vector<vector<bool>> &vis, int cnt)
{
    if (i == 6 && j == 0)
    {
        if (cnt == 48)
            ans++;
        return;
    }

    if ((i == 6 || vis[i + 1][j]) && (i == 0 || vis[i - 1][j]) && (j != 6 && !vis[i][j + 1]) && (j != 0 && !vis[i][j - 1]))
        return;

    if ((j == 6 || vis[i][j + 1]) && (j == 0 || vis[i][j - 1]) && (i != 6 && !vis[i + 1][j]) && (i != 0 && !vis[i - 1][j]))
        return;

    for (int k = 0; k < 4; k++)
    {
        int ii = i + dir[k], jj = j + dir[k + 1];

        if (ii >= 0 && jj >= 0 && ii < 7 && jj < 7 && !vis[ii][jj] && (s[cnt] == '?' || s[cnt] == dic[k]))
        {
            vis[ii][jj] = true;
            paths(ii, jj, vis, cnt + 1);
            vis[ii][jj] = false;
        }
    }
}

int main()
{
    fast;

    cin >> s;
    // s="??????R??????U??????????????????????????LD????D?";
    ans = 0;

    vector<vector<bool>> vis(7, vector<bool>(7, false));

    vis[0][0] = true;
    paths(0, 0, vis, 0);

    cout << ans;

    return 0;
}
1 Like
#6

(What I would have posted if this hadn’t been resolved)

The debugging module mentions the following:

Go through the algorithm for a simple case / write some testcases to run your algorithm on.

Here a “simple case” might mean running your code on a 3\times 3 grid and adding print statements to your dfs function.

1 Like