If provided a matrix that represents a maze with 2s being potential passes, 1s u

Question

If provided a matrix that represents a maze with 2s being potential passes, 1s unexplored terrirory and 0s being walls, How would one make a method that provides a straight forward path following the 2s, without hitting dead ends? For example an easy example would be matrix below, where coordinates are displayed to display a path. 0,0 is the top left and 4,4 is the bottom right.

20010
22200
02001
02220
02022

The method would display these results: (0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3), (4,3), (4,4)

Explanation / Answer

/*This is a C++ implementation of the problem. However the solveMaze function should be fairly similar in any language */

#include <iostream>
/*Hard coding the matrix dimension for ease of uderstanding*/
#define N 5   

using namespace std;

/*This matirx is used to keep track of the path traversed by updating its contents from 0 to 1. I have made it global only to make the solution less complicated. It may be passed along to solveMaze if defined within main()*/
int sol[N][N] = {0};

/*The solution method*/
bool solveMaze(int maze[N][N], int x, int y)
{
    /*if (x,y is exit) we return true*/
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }

    /* Check if maze[x][y] is within bounds and has a value of 2*/
    /*If it is possible to walk through 1s as well, replace the velow condition with the following: if(x >= 0 && x < N && y >= 0 && y < N && (maze[x][y] == 2 || maze[x][y] == 1)*/
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 2)
    {
        /* We assume x,y as part of solution path */
        sol[x][y] = 1;

        /* We try to move forward in x direction */
        if (solveMaze(maze, x+1, y) == true)
            return true;

        /* If moving in x direction doesn't give solution then move down in y direction */
        if (solveMaze(maze, x, y+1) == true)
            return true;

        /* If none of the above movements work, the assumption was wrong and then we BACKTRACK and unmark x,y as part of solution path */
        sol[x][y] = 0;
        return false;
    }

    return false;
}

/* Driver program to test above function. I have hard coded both the matrix and its dimensions as the request was only for the implementation of the method*/
int main()
{
    int maze[N][N] = { {2, 0, 0, 1, 0},
        {2, 2, 2, 0, 0},
        {0, 2, 0, 0, 1},
        {0, 2, 2, 2, 0},
        {0, 2, 0, 2, 2},
    };

    /*Start the solution by passing 0,0 as the entry point*/
    if(solveMaze(maze, 0, 0) == false)
        cout << "No solution";
    else
    {
        /*We print the position where our solution matrix holds a value of 1. This gives the path traversed*/
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                if(sol[i][j] == 1)
                    cout << "(" << i << ", " << j << ") ";
        }
    }
    return 0;
}

Output:

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.