How can I sort out runtime error in my code involving DFS

Question

I am a student learning C++ as my major language. I'm eager to improve and I would greatly appreciate any feedback. I'm trying to solve an algorithm problem which seems to involve Depth First Search.

To briefly explain what the question is about, there is a 2d array initially entered (with its number of rows and columns), consisted of only '0' and '1'. The array itself represents a maze at which I'm only allowed to follow the path continued by 1. (0 represents the wall that blocks my path.)

e.g.

In this way, I start from the top left (0,0) and I have to get to the bottom right (4, 6) where the path ends. It is guaranteed that every maze has at least one path that I can make it through the end, and my job is to search the the minimum number of '1' blocks that I have to pass during the optimum path. (You can move in all direction, NESW, but you can't go diagonal.)

I assumed the solving must be done using DFS, and here is the code:

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

int n, m;
vector<string>grid; // I used vector to store the 2d array

int dfs(int x, int y, int count, map<pair<int, int>, bool>searchPath) { // Recursive function to perform DFS.
    vector<int>num; //This vector will store 4 numbers in each cycle, where these are numbers   of 1 blocks that will be passed for 4 direction: N, S, E, and W.  
    bool atLeast = false; // boolean to check if at least one of 4 directions meets the condition
    count++;
//searchPath is a map to indicate that the path was already taken that it can't be passed again. This prevents the code from getting stuck in infinite loop.

    if (grid[x - 1][y] == '1' && !searchPath[make_pair(x - 1, y)]) { //check if the block at the specific direction to me is not 0 and the block was already passed before. 
        map<pair<int, int>, bool>searchPath2(searchPath); 

// copy of the map, and this will be used as an argument for the next recursive loop. 
        atLeast = 1;
        searchPath2[make_pair(x - 1, y)] = true; //indicate this block is now taken 
        int val1 = dfs(x - 1, y, count, searchPath2); //Run the subsequent recursive loop where now I'm at the block that was at my left side.  
        if (val1 != 0) { //If the path starting from that block seems to have a solution, store it to the vector, num where I will find the minimum element and return it at the end of the function. 
            num.push_back(val1); //store the number of 1 blocks that will be passed if I make a decision to go west
        }
    }
    if (grid[x + 1][y] == '1'  && !searchPath[make_pair(x + 1, y)]) {
        atLeast = 1;
        if (x + 1 == n && y == m) {
            return count;
        }
        map<pair<int, int>, bool>searchPath2(searchPath);
        searchPath2[make_pair(x - 1, y)] = true;
        int val2 = dfs(x + 1, y, count, searchPath2);
        if (val2 != 0) {
            num.push_back(val2);
        }
    }
    if (grid[x][y - 1] == '1'  && !searchPath[make_pair(x, y - 1)]) {
        atLeast = 1;
        map<pair<int, int>, bool>searchPath2(searchPath);
        searchPath2[make_pair(x, y - 1)] = true;
        int val3 = dfs(x, y - 1, count, searchPath2);
        if (val3 != 0) {
            num.push_back(val3);
        }
    }
    if (grid[x][y + 1] == '1'  && !searchPath[make_pair(x, y + 1)]) {
        atLeast = 1;
        if (x == n && y + 1 == m) {
            return count;
        }
        map<pair<int, int>, bool>searchPath2(searchPath);
        searchPath2[make_pair(x, y + 1)] = true;
        int val4 = dfs(x, y + 1, count, searchPath2);
        if (val4 != 0) {
            num.push_back(val4);
        }
    }
    if (!atLeast) {
        return 0;
    }

    else {
        return *min_element(num.begin(), num.end());
    }
}

int main(void) {
    cin >> n >> m;
    grid.resize(n);
    for (auto &iter : grid) {
        cin >> iter;
    }
    map<pair<int, int>, bool>searchPath;
    searchPath[make_pair(0, 0)] = true;
    cout << dfs(0, 0, 0, searchPath);
    return 0;
}

The code seems to have a runtime error. Here is the error sign:

/tmp/program/run.sh: line 1: 178 Segmentation fault ./prog Command exited with non-zero status 139

Which line is the problem?

See here please: https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems?r=Saves_AllUserSaves You can't expect volunteers participating here to do this work for you in 1st place. When you've done it, you may provide a [mcve], if something from your observations and debugging is still unclear for you. — πάντα ῥεῖ, Apr 15 '23 at 12:06
`if (grid[x - 1][y]` How's that going to work when `x == 0`? — Retired Ninja, Apr 15 '23 at 12:12
The function shouldn't do anything if (x,y) is not a valid coordinate (i.e. the base case of your recursion) — molbdnilo, Apr 15 '23 at 12:28
*178 Segmentation fault* -- Looking at your code, it doesn't explicitly use pointers, only `map`, `vector`, etc. Thus the probable reason for this error is that you are going out-of-bounds of the vector. Thus what you should do is to slowly replace where you are accessing the vectors using `[]`, and instead use the `at()` function. What will eventually happen is that a `std::out_of_range` exception will be thrown instead of a seg fault, indicating where you are going out-of-bounds. For example:`grid.at(x).at(y + 1)` instead of `grid[x][y + 1]`. — PaulMcKenzie, Apr 15 '23 at 12:59

score 0 · Answer 1 · answered Apr 15 '23 at 12:34

In the first iteration, when x == 0 and y == 0, you are trying to read from the searchPath map for -1, 0 however the map only contains an entry for 0, 0! You should set the whole map to false (except for (0, 0)) before calling dfs.

Also if x == 0 or y == 0 or x == n - 1 or y == m - 1, you should not check that coordinate, as it is outside the grid. And will crash the program too!

Lastly, if num.size() == 0, this line will not work: return *min_element(num.begin(), num.end());

How can I sort out runtime error in my code involving DFS

1 Answers1