c++ - 使用递归在迷宫中找到路径

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

1. 在 if(maze[coorx][coory+1]=0)(以及类似的)path() 语句中，单个等号是赋值运算符，因此它的计算结果始终为 false。

   由于 maze 是一个 bool 数组，您应该只使用 if(!maze[coorx][coory + 1])。

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

3. 在 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 将在递归结束时向后，但您可以将其反转。

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

5. if(maze[1][1]==1) in main() 应该是 if(maze[0][ 0]) 而不是，因为您显然是想从左上角的单元格开始。

编辑:

1. 一旦递归工作，您可以简单地在 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...
   }
   

2. 您在 main() 中调用了三次 path()。只需调用一次并将结果存储在 bool 值中。

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