尝试复制迷宫算法

Question

我正在尝试使用回溯让我的 C 程序解决迷宫问题。

基本上，程序所做的是将一个文件作为命令行参数插入（该文件应包含迷宫结构）并尝试“解决它”，输出每一步。

迷宫墙是 hashtags (#)，程序应该避开它们。每一步都应该用 dot (.) 标记。程序只能踩空格( ).

迷宫从符号S (Start)开始，应该到达符号E (End)。

迷宫的外观示例如下：

迷宫数据存储在一个矩阵a[1000][1000]中，1000在我的程序中定义为MAX。每次我在矩阵a[y][x]上的某个位置做一步，a[y][x]应该转化为dot (.).

我正在使用 usleep() 函数，每隔 80 000 nanoseconds 输出矩阵，以便用户可以正确地看到每一步。

一切正常（几乎正常）。当迷宫到达某一点无法继续前进时，它会删除之前的所有步骤，直到找到另一条路。问题是，它删除的“点”比它打算删除的要多。而且（我认为）这就是它永远不会达到 E 点的原因。

代码相关信息：

这些是我的全局变量声明：

int i_MAX, j_MAX;

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

其中 i_MAX 和 j_MAX 用于计算迷宫数组的大小 a。

main()函数仅包含从命令行参数获取文件的过程，计算i_MAX和j_MAX，以及调用back(0).

这些是（在我看来）造成麻烦的函数：

int is_acceptable(int step_Y, int step_X, int i, char a[MAX][MAX]) {
    // check if it is possible to move the current point (step_X, step_Y)
    // to the position (step_X+dx[i], step_Y+dy[i])
    step_Y += dy[i];
    step_X += dx[i];
    if (a[step_Y][step_X] == ' ' && step_Y >= 0 && step_X >= 0 
                                 && step_Y < i_MAX && step_X < j_MAX)
        return 1;
    return 0;
}

int is_solution(int step_Y, int step_X) {
    if (step_Y == i_MAX && step_X == j_MAX) return 1;
    return 0;
}

void bck(int step_Y, int step_X, char a[MAX][MAX]) {
    // test
    system("clear");
    for (int w = 0; w<i_MAX; w++) {
            for(int x = 0; x<j_MAX; x++)
            putchar(a[w][x]);
        printf("\n");
    }
    usleep(80000);
    // end test
    for (int i = 0; i<=3; i++) {
        if (is_acceptable(step_Y, step_X, i, a)) {
            step_Y += dy[i];
            step_X += dx[i];
            a[step_Y][step_X] = '.';
            if (is_solution(step_Y, step_X)) {
                for (int w = 0; w<i_MAX; w++) {
                    for(int x = 0; x<j_MAX; x++)
                        putchar(a[w][x]);
                printf("\n");
                }
            }
            else bck(step_Y, step_X, a);
            a[step_Y][step_X] = ' ';
        }
    }
}

我很确定问题出在 bck() 函数的最后一行，当试图“重置”无效位置时：

a[step_Y][step_X] = ' ';

我尝试了多种方式更改该行，但仍然无法使程序正常运行。

我做错了什么？是否与代码的其他部分有关？

P.S。这是我的迷宫文字：

################################################################################
#S                                                                  #          #
################################################################### # ######## #
#                                                           ####### # ##    ## #
# ######################################################### #       # ## ## ## #
# # #E                                                    # ####### # ## ## ## #
# # ##################################################### #         # ## #  ## #
# #                                                       ######### # ## ## ## #
# ####################################################### # #       # ## ## ## #
# #                                                         # ##### # ## ## ## #
# # ####################################################### # # ### # ## ## ## #
# # #        #########################                      # #     # ## ## ## #
# # # ######                         ######################## ##### # ## ## ## #
# # # ## ### ####################### # ##     ###     ##    ##    # # ## ## ## #
# # #  #     #                       #    ###     ###    ##    #### # ## ## ## #
# # ## ############################# # ############################ # ## ## ## #
# # ## #                        ###  #                            # # ## ## ## #
# # ## # ########### ############   ## ############################## ## ## ## #
# #    #           # #            ####                                #  ###   #
# ################ # ####### ######### ##############################   #### # #
#                # # #                                            # ########## #
######## ######### # ############################################## #          #
#                  #                                                  ### ######
################################################################################

Answer 1

函数：is_solution

E(end)不一定是i_MAX和j_MAX。在您的示例中，它是 step_Y=5 和 step_X=5

函数：bck

递归问题：在递归调用 bck 之前更改 step_X ans step_Y。但是，如果这条路是死胡同，在尝试另一个方向之前，你必须将 step_X 和 step_Y 恢复到它们的原始值。

void bck (int step_Y, int step_X, char a[MAX][MAX]) {
    // test
    ...
            else bck(step_Y, step_X, a);
            a[step_Y][step_X] = ' ';
            step_Y -= dy[i];
            step_X -= dx[i];
        }
    }
}

尝试复制迷宫算法

Trying to replicate a maze algorithm

c

maze

backtracking

recursive-backtracking