find a path in maze using recursion

Question

Hi~I got stuck in this problem. Someone please help me!!!!

The problem is that the program will ask the user to input a number between 4 and 20 to decide the size of the maze. It will later ask the user to input the contents of the maze row by row and store it into a 2D bool array (true means blocked and false means clear). Then the program starts at the top left corner and tries to find a path leading to the lower right corner (can move right, left, up, down). At this time, the program should also maintain another char array which record the path found (if there's any) and print it out at the end of processing. This problem asks to use recursion to solve it.

Here's what I got now:

#include<iostream>

using namespace std;

int row, col;
int size=0;
bool  maze[21][21]; 
char print[22][22];
const char start = 's', up = 'u', down = 'd', left = 'l', right = 'r', barrier = 'x';

char path(int coorx, int coory, int size)
{
    if(maze[coorx][coory+1]=0)
    {   
        print[coorx+1][coory+2]='r';
        return path(coorx,coory+1,size);
    }
    else
    {
        if(maze[coorx+1][coory]=0)
        {
            print[coorx+2][coory+1]='d';
            return path(coorx+1,coory,size);
        }
        else
        {
            if(maze[coorx][coory-1]=0)
            {
                print[coorx+1][coory]='l';
                return path(coorx,coory-1,size);
            }
            else
            {
                if(maze[coorx-1][coory]=0)
                {
                    print[coorx][coory+1]='u';
                    return path(coorx-1,coory,size);
                }
            }
        }
    }
}

int main()
{

    while(size<4 || size>20) 
    {
        cout<<"Please input size of maze (a number between 4 and 20 is expected) -> ";
        cin >>size;

        if(size<4 || size>20)
            cout<<"**Error** maze size not in range!"<<endl;
    }

    cout<<"Please input contents of maze row by row, 1 for barrier and 0 for free passage."<<endl;
    cout<<endl;
    for(int i=1; i<size+1; i++)
    {
        for(int j=1; j<size+1; j++)
            cin>>maze[i][j];
    }

    if(maze[1][1]==1)
        cout<<"**Error** entrance to maze is blocked!"<<endl;
    else
    {
        // find the path
        for(int coorx=0;coorx<size;coorx++)
        {
            for(int coory=0;coory<size;coory++)
                path(coorx,coory,size);
        }


        cout<<"The maze and the path:"<<endl;

        // print the forum (adding characters '+','-', ' ')
        print[0][0]=print[size+1][size+1]=print[0][size+1]=print[size+1][0]='+';
        print[1][1]='s';
        for(int x=1; x<size+1; x++)
        {
            for(int y=0; y<size+2; y++){
                if(y==0 || y==size+1)
                {
                        print[x][y]='|';
                }
            }

        }

        for(int x=0; x<size+2; x++)
        {
            for(int y=0; y<size+2; y++){
                if(x==0 || x== size+1){
                    if(y!=0 && y!=size+1)
                    print[x][y]='-';
                }
            }

        }


        for(int row=0; row<size+2; row++)
        {
            for(int col=0; col<size+2; col++)
            {
                if(maze[row][col]==1)
                    print[row][col]='x';
            }
        }

        // print out the record of the path found
        for(int row=0; row<size+2; row++)
        {
            for(int col=0; col<size+2; col++){
                cout<<print[row][col];
            }

            cout << endl;
        }
    }
    return 0;
}

I don't know why I can't show those 'r', 'd', 'l', 'u'. I already assigned them to print[][], but why it won't show why I print out the print[][]??

New coding

#include<iostream>
using namespace std;

int row,col;
int size=0;
bool  maze[20][20]; 
char print[22][22];

bool path(int coorx, int coory, int size)
{
if(coorx==size-1 && coory==size-1)
    return true;
if(!maze[coorx][coory+1] && path(coorx,coory+1,size))
    return true;
    return 'r';
if(!maze[coorx+1][coory] && path(coorx+1,coory,size))
    return true;
    return 'd';
if(!maze[coorx][coory-1] && path(coorx,coory-1,size))
    return true;
    return 'l';
if(!maze[coorx-1][coory] && path(coorx-1,coory,size))
    return true;
    return 'u';
}

int main()
{

while(size<4 || size>20) 
{
    cout<<"Please input size of maze (a number between 4 and 20 is expected) -> ";
    cin >>size;

    if(size<4 || size>20)
        cout<<"**Error** maze size not in range!"<<endl;
}

cout<<"Please input contents of maze row by row, 1 for barrier and 0 for free passage."<<endl;
cout<<endl;
for(int i=0; i<size; i++)
{
    for(int j=0; j<size; j++)
        cin>>maze[i][j];
}

if(maze[0][0]==1)
    cout<<"**Error** entrance to maze is blocked!"<<endl;
else
{
    int row=0;
    int col=0;
    path(row,col,size);

    if(!path(row,col,size))
    {
        cout<<"**Warning** no path from entrance to exit!"<<endl;
    }
    else
    {
        if('r')
            print[row+2][col+3]='r';
        if('d')
            print[row+3][col+2]='d';
        if('l')
            print[row+2][col+1]='l';
        if('u')
            print[row+1][col+2]='u';
    }

    cout<<"The maze and the path:"<<endl;

    // print the forum (adding characters '+','-', ' ')
    print[0][0]=print[size+1][size+1]=print[0][size+1]=print[size+1][0]=='+';
    print[1][1]='s';
    for(int x=1; x<size+1; x++)
    {
        for(int y=0; y<size+2; y++){
            if(y==0 || y==size+1)
            {
                    print[x][y]=='|';
            }
        }

    }

    for(int x=0; x<size+2; x++)
    {
        for(int y=0; y<size+2; y++){
            if(x==0 || x== size+1){
                if(y!=0 && y!=size+1)
                print[x][y]=='-';
            }
        }

    }


    for(int row=0; row<size; row++)
    {
        for(int col=0; col<size; col++)
        {
            if(maze[row][col]==1)
                print[row+1][col+1]=='x';
        }
    }

    path(0,0,size);

    // pirnt out the record of the path found
    for(int row=0; row<size+2; row++)
    {
        for(int col=0; col<size+2; col++){
            cout<<print[row][col];
        }

        cout << endl;
    }
}
return 0;
}

for maze size=4

the sample run looks like

s r r r
      d
      d
      d

but my program run like this

s r

nothing afterward, don't know why

irrelephant irrelephant · Accepted Answer · 2014-11-07T19:05:27

In your if(maze[coorx][coory+1]=0) (and similar) statements in path(), the single equals is the assignment operator, so it'll always evaluate to false.

Since maze is a bool array, you should just use if(!maze[coorx][coory + 1]).
print should probably be a one dimensional array instead of a two dimensional array since it only needs to keep track of "r", "l", "d", and "u", and not the cells where you take those actions.

In path(), you're returning early instead of backtracking. You should return only if a path exists, and you can tell whether a path exists by recursing.

In other words, the path() function needs to be rewritten to look something like this:

/* returns true if there's a path to the bottom right cell, otherwise false */
bool path(int coorx, int coory, int size) {
    if(coorx == size - 1 && coory == size - 1) { // exit of maze
        return true;
    }
    if(!maze[coorx][coory + 1] && path(coorx, coory + 1, size)) {
        // add "right" to your path
        return true;
    }
    if(!maze[coorx + 1][coory] && path(coorx + 1, coory, size)) {
        // add "down" to your path
        return true;
    }
    // etc...
}

Of course, you should add bounds checking as well.

And, path will be backwards at the end of the recursion, but you can just reverse it.

You should call the path() function just once at the top left cell, not at each and every cell. Recursion will handle the search through all cells of the maze.
if(maze[1][1]==1) in main() should probably be if(maze[0][0]) instead, since you're apparently trying to start at the top left cell.

Edit:

Once you get the recursion working, you can simply add to print in path():

bool path(int coorx, int coory, int size, int depth) {
    // if(coorx == size - 1 ... base case
    if(!maze[coorx][coory + 1] && path(coorx, coory + 1, size, depth + 1)) {
        print[coorx][coory + 1] = 'r';
        return true;
    }
    // etc...
}

You're calling path() three times in main(). Just call it once and store the result in a boolean.
You're not printing the path correctly. The sample output prints out the character for each cell in print -- you should do the same.

find a path in maze using recursion

1 Answers

Edit: