使用递归在迷宫中寻找路径

Question

嗨~我被这个问题困住了。有人请帮帮我！！！！

问题是程序会要求用户输入一个4到20之间的数字来决定迷宫的大小。它稍后会要求用户逐行输入迷宫的内容并将其存储到2D bool数组中（true表示阻塞，false表示清除）。然后程序从左上角开始，并尝试找到一条通往右下角的路径（可以向右、向左、向上、向下移动）。此时，程序还应该维护另一个char数组，该数组记录找到的路径（如果有的话）并在处理结束时打印出来。这个问题要求使用递归来解决它。

这是我现在得到的：

#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;
}

我不知道为什么我不能显示这些“r”、“d”、“l”、“u”。我已经将它们分配给print[][]，但为什么它不会显示为什么我打印出print[][]？

新编码

#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;
}

迷宫大小=4

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

示例运行看起来像

s r r r
      d
      d
      d

但我的程序是这样运行的

s r                        

之后什么都没有，不知道为什么

Answer 1

>

在path（）中的if（maze[coorx][coory 1]=0）（以及类似的）语句中，单个equals是赋值运算符，因此它的计算结果总是为false。

因为maze是一个布尔数组，所以如果（！maze[coorx][coury 1]），就应该使用if（！maze[coorx][coury 1]）。

print可能应该是一维数组而不是二维数组，因为它只需要跟踪“r”、“l”、“d”和“u”，而不需要跟踪执行这些操作的单元格。

在path（）中，您是提前返回而不是回溯。您应该仅在路径存在时返回，并且您可以通过递归来判断路径是否存在。

换句话说，需要重写path（）函数，使其看起来像这样：

/* 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...
}

当然，您也应该添加边界检查。

并且，path将在递归结束时向后，但您可以将其反转。

您应该只在左上方的单元格调用path（）函数一次，而不是在每个单元格。递归将处理迷宫中所有单元格的搜索。

if（maze[1][1]==1）在main（）中应该是if（maze[0][0]），因为你显然是想从左上角的单元格开始。

一旦递归开始工作，只需在path（）中添加到print：

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...
}

您在main（）中调用path（）三次。只需调用一次并将结果存储在布尔值中。

您没有正确打印路径。示例输出打印出print中每个单元格的字符——您也应该这样做。