C++ No output Grid Paths

Question

I was trying to recursively find the path from upper-left corner to lower-left corner of a grid that traverses through all values. So for example, I have a 2x2 grid, and it should go Right, Down, Left, and this is the only solution. For some reason, when I run my program I get no output after some pause, and I changed it to a smaller grid, and added the output of the direction for each recursive call for debugging purposes, but the program doesn't output anything.

Shouldn't it at least output something when it goes through the first if-statement? I'm unsure what is wrong.

#include <bits/stdc++.h>

using namespace std;

int grid[4];
vector<char> path;
int counter = 0;

void search(int n) {
    if (path.size() == 3 && n == 2) {
        for (auto x : path) {
            cout << x;
        }
        cout << "\n";
    }
    if (path.size() == 3 || n == 2) return;
    grid[n] = 1;
    // Go Up
    if (n-2 >= 0 && n-2 <= 3 && !grid[n-2]) {
        path.push_back('U');
        cout << 'U';
        search(n-2);
    };
    path.pop_back();
    // Go Down
    if (n+2 >= 0 && n+2 <= 3 && !grid[n+2]) {
        path.push_back('D');
        cout << 'D';
        search(n+2);
    };
    path.pop_back();
    // Go Left
    if (n-1 >= 0 && n-1 <= 3 && !grid[n-1]) {
        path.push_back('L');
        cout << 'L';
        search(n-1);
    };
    path.pop_back();
    // Go Right
    if (n+1 >= 0 && n+1 <= 3 && !grid[n+1]) {
        path.push_back('R');
        cout << 'R';
        search(n+1);
    };
    path.pop_back();
}

int main() {
    search(0);
    cout << counter;
    return 0;
}

What's asked here is really testing basic knowledge and understanding of computer science and algorithms. If you don't know the answer, a bare code dump that implements this will not really help you to understand anything, or learn anything. Instead, the correct answer here should be to go and learn the relevant areas of computer science and algorithms which are needed to implement this. Unfortunately, stackoverflow.com is not a replacement for a [good C++ and computer science algorithms textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Dec 22 '20 at 02:24

score 0 · Answer 1 · answered Dec 22 '20 at 02:30

0

Path is never initialized. So when you evaluate that first if statement, it will not succeed since path.size() is actually 0.

Initialize path to some list of length 3, and then the if statement you are talking about would run.

answered Dec 22 '20 at 02:30

Henri

145
13

C++ No output Grid Paths

1 Answers1