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

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



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

• Include a link to the problem
• Format your post (especially code blocks)
• Include what you’ve tried so far

What’s this?

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

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

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

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

(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