Algorithm using DFS

Question

im trying to solve this, its stuck in a loop but i cant understand why. I think i might need to add some more conditions and i have looked others people's code but they seem too complicated.

    function solve(m, s, x, y) {        
        if (x == 9 && m[x][y] == "1") 
        {return;} //if last row, found door
    
    
        if (m[x+1][y] == "1") { //down
            s.push([x+1] + ", " + [y]);
            solve(m, s, x+1, y);
        }
    
        if (m[x][y+1] == "1") { //left
            s.push([x] + ", " + [y+1]);
            solve(m, s, x, y+1);
        }
    
        if (m[x][y-1] == "1") { //right
            s.push([x] + ", " + [y-1]);
            solve(m, s, x, y-1);
        }
    
        if (matrix[x-1][y] == "1") {  //up
            s.push([x-1] + ", " + [y]);
            solve(m, s, x-1, y);
        }
        s.pop(); //if bad path with no end
    }

@Aldert yes but i am not sure how to fix, am currently looking at an answer here — Bryar
– Bryar, Commented Nov 25, 2021 at 18:16
Please add a programming-language tag, and post minimal reproducible example, including hard-coded test data. Consider using meaningful parameters names. — c0der
– c0der, Commented Nov 26, 2021 at 7:46

trincot · Accepted Answer · 2021-11-25 20:56:01Z

1

The problem is that you don't mark which cells you have visited, and so you will revisit the same cell again, leading to a non-ending back-and-forth moment between coordinates 4,8 and 4,9.

One way to solve that, is to leave a trace in the matrix with another value, like value 2:

    // ...
    if (x == 9 && matrix[x][y] == "1") {    
        { return; } //if last row, found door

    matrix[x][y] = 2; // mark as visited <-- add this
    // ...

Some other issues:

You should implement backtracking in way that the caller knows whether the recursive search was successful or not. So let your function return something that indicates this, like a boolean. Only when that return value is true, exit. Otherwise, the alternative directions should still be tried, and if no alternatives exist, the pop should happen with a return of false. Also the base cases should return true or false.
The range checks should not be done with literals like 9, but be dynamic, so they check the actual size of the input array.

let stack = [];
let matrix = [  
                [0, 1, 0, 0, 0, 0],
                [0, 1, 0, 0, 0, 0],
                [0, 1, 0, 1, 0, 0],
                [1, 1, 1, 1, 0, 0],
                [1, 0, 0, 0, 0, 0],
                [1, 0, 0, 0, 0, 0],        
             ];

function solve(matrix, stack, x, y) {
    if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) {
        return false;
    }

    if (x == matrix.length - 1 && matrix[x][y] == "1") {    
        return true; //if last row, found door
    }
    matrix[x][y] = 2; // mark as visited

    if (matrix[x+1][y] == "1") { //down
        stack.push([x+1] + ", " + [y]);
        if (solve(matrix, stack, x+1, y)) return true;
    }

    if (matrix[x][y+1] == "1") { //left
        stack.push([x] + ", " + [y+1]);
        if (solve(matrix, stack, x, y+1)) return true;
    }

    if (matrix[x][y-1] == "1") { //right
        stack.push([x] + ", " + [y-1]);
        if (solve(matrix, stack, x, y-1)) return true;
    }

    if (matrix[x-1][y] == "1") {  //up
        stack.push([x-1] + ", " + [y]);
        if (solve(matrix, stack, x-1, y)) return true;
    }
    stack.pop(); //if bad path with no end
    return false;
}


function detectStart(matrix, stack) {
    for (let y = 0; y < matrix.length; y++) {
        if (matrix[0][y] === 1) {
            stack.push([0] + ", " + [y]);
            solve(matrix, stack, 0, y);
            console.log(stack);
            return;
        }
    }
}

detectStart(matrix, stack);

Some other remarks:

it is a bit strange that you compare matrix values with strings, while you initialise the matrix with numeric values.
You could avoid some code repetition and do the check for 1 in the cell and the subsequent push at the start of the function, instead of doing that before the (recursive) call.

edited Nov 25, 2021 at 20:56

answered Nov 25, 2021 at 18:13

trincot

357k38 gold badges282 silver badges339 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Bryar Over a year ago

i have been all day working with this and one line its all it took, thank you so much. T_T

Bryar Over a year ago

Hey Im still debugging with that line, and now i realized it will sometimes block access to other cells, and only half the path will be checked. Not sure if u got any suggestions

trincot Over a year ago

If it would block access to other cells, then you should find the path on backtracking to that cell. Can you give an example grid with this problem?

trincot Over a year ago

I added some points to my answer.

Bryar Over a year ago

Thats well thought! i was considering of returning booleans but was unsure if it would make a big difference. Thanks!!

|

Vadim Chernetsov · Accepted Answer · 2021-12-18 11:42:31Z

Here is the solution of the current problem, created by Mr. trincot. The implementation is in C++.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int maximumSize=6;
vector<vector<int>> matrix={{0, 1, 0, 0, 0, 0},
                            {0, 1, 0, 0, 0, 0},
                            {0, 1, 0, 1, 0, 0},
                            {1, 1, 1, 1, 0, 0},
                            {1, 0, 0, 0, 0, 0},
                            {1, 0, 0, 0, 0, 0}};
vector<vector<int>> visited(maximumSize, vector<int>(maximumSize, 0));
vector<tuple<int, int>> path;
void showContentVector2D(vector<vector<int>>& input)
{
    for(int i=0; i<input.size(); ++i)
    {
        for(int j=0; j<input[i].size(); ++j)
        {
            cout<<input[i][j]<<", ";
        }
        cout<<endl;
    }
    return;
}
void showContentVectorTuple(vector<tuple<int, int>>& input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<get<0>(input[i])<<" : "<<get<1>(input[i])<<endl;
    }
    return;
}
void dfs(int indexX, int indexY)
{
    if(indexX<0 || indexX==matrix.size() || indexY<0 || indexY==matrix[0].size())
    {
        return;
    }
    if(indexX==(matrix.size()-1) && (matrix[indexX][indexY]==1))
    {
        visited[indexX][indexY]=1;
        auto indices=make_tuple(indexX, indexY);
        path.push_back(indices);
        return;
    }
    visited[indexX][indexY]=1;
    auto indices=make_tuple(indexX, indexY);
    path.push_back(indices);
    if(visited[indexX+1][indexY]==0)
    {
        if(matrix[indexX+1][indexY]==1)
        {
            dfs(indexX+1, indexY);
            if(visited[indexX+1][indexY])
            {
                return;
            }
        }
    }
    if(visited[indexX-1][indexY]==0)
    {
        if(matrix[indexX-1][indexY]==1)
        {
            dfs(indexX-1, indexY);
            if(visited[indexX-1][indexY])
            {
                return;
            }
        }
    }
    if(visited[indexX][indexY-1]==0)
    {
        if(matrix[indexX][indexY-1]==1)
        {
            dfs(indexX, indexY-1);
            if(visited[indexX][indexY-1])
            {
                return;
            }
        }
    }
    if(visited[indexX][indexY+1]==0)
    {
        if(matrix[indexX][indexY+1]==1)
        {
            dfs(indexX, indexY+1);
            if(visited[indexX][indexY+1])
            {
                return;
            }
        }
    }
    return;
}
void solve()
{
    for(int i=0; i<matrix.size(); ++i)
    {
        if(matrix[0][i]==1)
        {
            dfs(0, i);
        }
    }
    cout<<"visited <- "<<endl;
    showContentVector2D(visited);
    cout<<endl<<"matrix <- "<<endl;
    showContentVector2D(matrix);
    cout<<endl<<"path <- "<<endl;
    showContentVectorTuple(path);
    cout<<endl;
    return;
}
int main()
{
    solve();
    return 0;
}

Here is the result:

visited <- 
0, 1, 0, 0, 0, 0, 
0, 1, 0, 0, 0, 0, 
0, 1, 0, 0, 0, 0, 
1, 1, 0, 0, 0, 0, 
1, 0, 0, 0, 0, 0, 
1, 0, 0, 0, 0, 0, 

matrix <- 
0, 1, 0, 0, 0, 0, 
0, 1, 0, 0, 0, 0, 
0, 1, 0, 1, 0, 0, 
1, 1, 1, 1, 0, 0, 
1, 0, 0, 0, 0, 0, 
1, 0, 0, 0, 0, 0, 

path <- 
0 : 1
1 : 1
2 : 1
3 : 1
3 : 0
4 : 0
5 : 0

@trincot, Hello, respected Mr. trincot. Here is the solution, provided by you, with the implementation in C++, if you are interested.

Collectives™ on Stack Overflow

Algorithm using DFS

2 Answers 2

9 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related