解决迷宫回溯

Question

我正在尝试使用 C 中的回溯来解决迷宫问题。要解决迷宫问题，请遵循以下规则：

你从S的位置开始，需要往E的方向走
您只能继续“.”路径
转换所有'.'进入 '#' 包括 S 和 E

输入由一个 m x n 矩阵组成：输入示例：

11 11
+-+-+-+-+-+
S.|...|...|
+.+.+.+-+.+
|.|.|.....|
+.+-+-+-+.+
|...|.|...|
+.+.+.+.+-+
|.|...|.|.|
+.+-+.+.+.+
|...|.....E
+-+-+-+-+-+

预期的解决方案：

+-+-+-+-+-+
##|...|...|
+#+.+.+-+.+
|#|.|.....|
+#+-+-+-+.+
|###|.|...|
+.+#+.+.+-+
|.|###|.|.|
+.+-+#+.+.+
|...|######
+-+-+-+-+-+

我正在非常努力地解决它，但由于某种原因，一旦我到达迷宫中我不能去的地方，我的程序就不会返回 further.It 只是向所有方向走它看到“.”的地方

我的想法是从 S 的位置开始，并在每个递归步骤中使用我们原来的位置。如果我正在看的位置是“.”，我将从我站立的位置向所有方向移动。如果那一点不是我原来的立场。

我也认为当我回溯到一个十字路口时我遇到了问题。例如：

+-+-+-+-+-+
##|...|...|
+#+.+.+-+.+
|#|.|.....|
+#+-+-+-+.+
|0##|.|...|
+.+#+.+.+-+
|.|###|.|.|
+.+-+#+.+.+
|..1|######
+-+-+-+-+-+

想象一下，我在位置 0。我从 1 回溯，将 # 改回 '.'。我怎么能声明说你有 2 # 种可能返回，但你应该停止？

我的代码：

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

void *safeMalloc(int n) {
    void *p = malloc(n);
    if (p == NULL) {
        printf("Error: malloc(%d) failed. Out of memory?\n", n);
        exit(EXIT_FAILURE);
    }
    return p;
}


char ** readMatrix(int m,int n,int* startI,int* startJ,int* endI,int* endJ){
    char **arr = safeMalloc(m*sizeof(char *));
    int row;
    for (row=0; row < m; row++) {
        arr[row] = safeMalloc(n*sizeof(char));
    }
    int i,j;
    for(i=0;i<m;i++){
        for(j=0;j<m;j++){
            scanf(" %c",&arr[i][j]);
            if(arr[i][j]=='S'){
                *startI=i;
                *startJ=j;
            }
            if(arr[i][j]=='E'){
                *endI=i;
                *endJ=j;
            }
        }
        getchar();
    }

    return arr;
}

void printNumber(char **arr,int m,int n){
    int i,j;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            printf("%c", arr[i][j]);
        }
        printf("\n");
    }
}

void findPath(char** arr,int m,int n,int startI,int startJ,int endI,int endJ,int oldI,int oldJ){
    int i=startI,j=startJ;
    int stepsPossible=4;
            //going up
           if(i-1>=0){
                if((arr[i-1][j]=='.') && ((i-1!=oldI) || (j!=oldJ))){
                    arr[i][j]='#';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i-1,j,endI,endJ,oldI,oldJ);
                }else{
                    stepsPossible--;
                }
           }
           //going right

           if(j+1<n){
                if((arr[i][j+1]=='.') && ((i!= oldI) || (j+1!=oldJ))){
                    arr[i][j]='#';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i,j+1,endI,endJ,oldI,oldJ);
                }else{
                    stepsPossible--;
                }
           }
           //going left
           if(j-1>=0){
                if((arr[i][j-1]=='.') && ((i!= oldI) || (j-1!=oldJ))){
                    arr[i][j]='#';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i,j-1,endI,endJ,oldI,oldJ);
                }else{
                    stepsPossible--;
                }
           }

           //going down
            if(i+1<m){
                if((arr[i+1][j]=='.') && ((i+1!= oldI) || (j!=oldJ))){
                    arr[i][j]='#';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i+1,j,endI,endJ,oldI,oldJ);
                }else{
                    stepsPossible--;
                }
           }
        //if the next block is E then we can stop.
           if((arr[i-1][j]=='E') || (arr[i][j+1]=='E') || (arr[i][j-1]=='E') || (arr[i+1][j]=='E')){
                if(arr[i-1][j]=='E'){
                    arr[i-1][j]='#';
                }

                if(arr[i][j+1]=='E'){
                    arr[i][j+1]='#';
                }

                if(arr[i][j-1]=='E'){
                    arr[i][j-1]='#';
                }

                if(arr[i+1][j]=='E'){
                    arr[i+1][j]='#';
                }
                return;
            }


            if(stepsPossible==0){
                if(arr[i-1][j]=='#'){
                    arr[i][j]='.';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i-1,j,endI,endJ,oldI,oldJ);
                }else{
                    return;
                }

                if(arr[i][j+1]=='#' ){
                    arr[i][j]='.';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i,j+1,endI,endJ,oldI,oldJ);
                }else{
                    return;
                }

                if(arr[i][j-1]=='#' ){
                    arr[i][j]='.';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i,j-1,endI,endJ,oldI,oldJ);
                }else{
                    return;
                }

                if(arr[i+1][j]=='#' ){
                    arr[i][j]='.';
                    oldI=i;
                    oldJ=j;
                    findPath(arr,m,n,i+1,j,endI,endJ,oldI,oldJ);
                }else{
                    return;
                }
            }
}


int main()
{
    int m,n;
    scanf("%d %d",&m,&n);
    int startI,startJ,endI,endJ;
    char** arr;
    arr=readMatrix(m,n,&startI,&startJ,&endI,&endJ);
    findPath(arr,m,n,startI,startJ,endI,endJ,startI,startJ);
    printNumber(arr,m,n);
    return 0;
}

Answer 1

我建议使用 BFS，因为

BFS 将找到最短的解决方案。
DFS 对某些迷宫的处理非常非常差。

以下是针对您的案例的 BFS 的简短描述：

在您的迷宫中找到 'S' 并将其添加到队列中
当队列不为空时检查从队列中获取元素。用“#”替换元素。如果元素是 E，你就完成了。检查元素的邻居（上、下、左、右），如果是“.”，则加入队列。
如果队列为空且未找到E，则没有从S到E的直接路径

Answer 2

正确使用 return 值，因为您可以利用它来简化您的逻辑。为错误案例（需要回溯）和成功案例（到达终点）在 findPath 上选择不同的 return 值。

现在您可以在该函数的开头无条件地设置 #，并在回溯情况的最后无条件地重置回 .。

也不需要计算可能的方向，只检查某些调用是否return成功。

也不需要一遍又一遍地编写边界检查，如果你只是在函数开始时检查它们，你就可以毫无问题地传递无效坐标。

bool findPath(char** arr, size_t sx, size_t sy, int x, int y) {
    if (x < 0 || x >= sx || y < 0 || y >= sy) return false;
    if (arr[x][y] == 'E') {
        are[x][y] = '#';
        return true;
    }
    if (arr[x][y] != '.') return false;
    arr[x][y] = '#';
    bool success = findPath(arr, sx, sy, x-1, y) ||
        findPath(arr, sx, sy, x+1, y) ||
        findPath(arr, sx, sy, x, y-1) ||
        findPath(arr, sx, sy, x, y+1);
    if (!success) arr[x][y] = '.';
    return success;
}

回溯算法的实现通常都遵循相同的模式：

尝试简单地拒绝或接受当前的解决方案。
修改当前解决方案。
尝试变体。
如果不成功，请清理修改。

解决迷宫回溯

Solve a maze backtracking

c

maze

backtracking