迷宫求解算法不适用于4个方向

Question

这是我对经典迷宫问题的解决方案。如果我只允许2次移动（向下或向右）并且只使用这2次移动就可以建立一条路径，那么它的工作非常完美。但是，如果我想允许所有4种可能的移动（向下，向右，向左，向上），程序永远不会给出解决方案（似乎递归堆栈最终增长并溢出）。我尝试使用小到4x4的迷宫，但没有成功。你能帮助我吗？ #被封锁，.是免费的。为了增加允许的运动，增加或减少#define MOVES (2)到#define MOVES (4)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ROW (10)
#define COL (10)

int start_index[]={0,0};
int end_index[]={9,9};

// char maze[R][C]={ // Can't solve this maze with 4 allowable moves
//     {'.','#','.','.','.','.','.','.','.','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','.','.','#','#','#','#','#','#','.'}
// };

char maze[ROW][COL]={ // Can solve this maze with 2 allowable moves
    {'.','.','#','.','.','.','.','.','.','#'},
    {'#','.','.','.','.','.','.','.','.','.'},
    {'#','.','#','.','.','.','.','.','.','.'},
    {'#','.','#','.','.','.','.','.','.','.'},
    {'.','.','.','.','.','.','.','.','#','.'},
    {'.','.','#','.','.','.','.','.','.','#'},
    {'#','.','.','.','#','#','.','.','.','.'},
    {'#','.','#','.','.','#','.','.','.','.'},
    {'.','.','#','.','.','#','.','.','#','.'},
    {'.','.','#','.','.','.','.','.','.','.'}
};

char sol[ROW][COL]={
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}
};

int move_x[]={0,1,0,-1};
int move_y[]={1,0,-1,0};

#define MOVES (4)

bool is_safe(int x,int y);
bool is_target(int x,int y);
bool solve_maze(int x,int y);
void print_mazes(bool solvable);

int main(){
    printf("\nStarting");
    bool solvable=solve_maze(start_index[0],start_index[1]);
    print_mazes(solvable);
    printf("\nEnd.");
}

bool solve_maze(int x,int y){
    int next_x,next_y;
    static int count=0;
    bool tmp_res=false;
    sol[x][y]='.';
    printf("\n%d: (%d,%d)",count++,x,y);
    for(int i=0;i<MOVES;i++){
        next_x=x+move_x[i];
        next_y=y+move_y[i];
        if(is_safe(next_x,next_y)){
            if(is_target(next_x,next_y)){
                sol[next_x][next_y]='.';
                return true;
                }
            else{
                tmp_res=solve_maze(next_x,next_y);
                if(tmp_res){
                    sol[next_x][next_y]='.';
                    return true;
                }
                else{
                    sol[next_x][next_y]='#';
                }
            }
        }
    }
    return false;
}

bool is_safe(int x,int y){
    if(x<COL && y<ROW && maze[x][y]!='#')
    return true;
    else return false;
}

bool is_target(int x,int y){
    if(x==end_index[0] && y==end_index[1]) return true;
    else return false;
}

// prints the original maze and the solution
void print_mazes(bool solvable){
    printf("\n\n   <<%sSolvable>>",(solvable)? "":"Not ");
        printf("\n   0 1 2 3 4 5 6 7 8 9\t\t   0 1 2 3 4 5 6 7 8 9\n");

        for(int i=0;i<ROW;i++){
            printf("%d: ",i);
            for(int j=0;j<COL;j++)
                printf("%c ",maze[i][j]);

            printf("\t\t%d: ",i);
            for(int j=0;j<COL;j++)
                printf("%c ",sol[i][j]);
        printf("\n");
        }
        printf("   0 1 2 3 4 5 6 7 8 9\t\t   0 1 2 3 4 5 6 7 8 9 \n");
}

Answer 1

您应该在访问它们时立即标记您访问过的单元格（而不是在最后，就像使用sol[next_x][next_y]='#';一样。如果当前算法进入已经由较低框架输入的单元格，则无法返回当前算法堆栈，导致一定的无限循环（从而堆栈溢出）。

尝试在solve_maze做的第一件事是if (sol[x][y]=='#') return false;，第二件事是sol[x][y] = '#';。第一个声明：

if (sol[x][y]=='#') return false;

说“如果这个单元格被标记为已访问过，请不要重新访问它”。第二个声明：

sol[x][y] = '#';

称“将此单元标记为已访问”。或者，您可以使用'#'以外的某些字符将单元格标记为已访问。我不确定这是否是你想要的'#'指示（似乎它意味着指示不在出口的某些路径上的细胞，但实际上在可解决的迷宫中，所有可探测的细胞都在通向出口的某个路径上） 。