我的递归迷宫求解器无法正确识别起始位置

Question

我正在尝试为递归迷宫求解器编写代码。这就是我目前所拥有的：

const int NROWS = 5;
const int MCOLS = 12;
// Symbols:
// ' ' = open
// 'X' = blocked
// 'S' = start
// 'E' = goal
// '.' = path
// '+' = bad path
char maze[NROWS][MCOLS+1] = {
    {"S XXXXXXXXXX"},
    {"X  X   XX  X"},
    {"XX   XX X XX"},
    {"XX X       X"},
    {"XXXXXXXXXEXX"},
    };

void display_maze(void);
bool find_path(int x, int y);

int main()
{
    display_maze();
    if ( find_path(0, 0) == true )
        printf("Success!n");
    else
        printf("Failedn");
    display_maze();
    return 0;
}

void display_maze()
{
    int i;
    printf("MAZE:n");
    for ( i = 0; i < NROWS; i++ )
    printf("%.*sn", MCOLS, maze[i]);
    printf("n");
    return;
}

bool find_path(int x, int y)
{
    // If x,y is outside maze, return false.
    if ( x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1 ) return false;
    // If x,y is the goal, return true.
    if ( maze[y][x] == 'E' ) return true;
    // If x,y is not open, return false.
    if ( maze[y][x] != ' ' && maze[y][x] != 'S' ) return false;
    // Mark x,y part of solution path.
    maze[y][x] = '.';
    // If find_path North of x,y is true, return true.
    if ( find_path(x, y - 1) == true ) return true;
    // If find_path East of x,y is true, return true.
    if ( find_path(x + 1, y) == true ) return true;
    // If find_path South of x,y is true, return true.
    if ( find_path(x, y + 1) == true ) return true;
    // If find_path West of x,y is true, return true.
    if ( find_path(x - 1, y) == true ) return true;
    // Unmark x,y as part of solution path.
    maze[y][x] = '+';
    return false;
}

对于这个迷宫的迭代，它工作得很好。输出打印"成功"并显示从"S"到"E"的路径。

然而，我应该这样移动"S"的位置吗：

XXXXXXSXXXXX
X  X   XX  X
XXX  XX X XX
XX X       X
XXXXX XXXEXX

输出打印"失败"。我有一种感觉，从我写的递归代码来看，如果迷宫不能立即找到"或"S"，它就会自动失败。我只是不知道如何实现代码来继续搜索"S"。

另一个问题——正如您所看到的，我在.cpp文件中实现了一个样例迷宫。然而，我的最终目标是从一个.txt文件流式传输一个迷宫。因此，每个迷宫都有不同的尺寸。对我来说，使用向量而不是字符数组更有意义吗？

Answer 1

对于迷宫，

XXXXXXSXXXXX
X  X   XX  X
XXX  XX X XX
XX X       X
XXXXX XXXEXX

当您使用参数（0,0）调用find_path（）时，该参数在该位置包含X。所以

 if ( maze[y][x] != ' ' && maze[y][x] != 'S' ) return false;

在find_path（）中执行，返回false。因此输出为失败。

您必须找到"S"的位置，然后使用这些参数调用find_path（）。

对于您的第二个问题：

您也可以使用矢量或STL字符串。如果您知道.txt文件中给定的最大行数，您也可以使用字符类型数组。

Answer 2

好吧，我根据您的代码做了一些更改

enum FromDirection{
    Origin,
    North_dir,
    East_dir,
    South_dir,
    West_dir,
 }
int main()
{
    display_maze();
    int find_result = find_path(0, 0, Origin);
    if ( find_result == true )
        printf("Success!n");
    else
        printf("Failedn");
    display_maze();
    return 0;
}
bool find_path(int x, int y, int ifrom_dir)
{
    static bool find_enterence = false;
    // If x,y is outside maze, return false.
    if ( x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1 ) return false;
    // If x,y is the goal, return true.
    if ( maze[y][x] == 'E' ) return true;
    // If x,y is not open, return false.
    if ( maze[y][x] != ' ' && maze[y][x] != 'S' ) {
        if( find_enterence){
            return false;
        }
        // check last position in case of backtracking
        if (ifrom_dir != North_dir && find_path(x, y - 1, South_dir)){
            return true;
        }
        if(ifrom_dir != East_dir && find_path(x + 1, y, West_dir)){
            return true;
        }
        if(ifrom_dir != South_dir && find_path(x, y+ 1, North_dir)){
            return true;
        }
        if (ifrom_dir != West_dir && find_path(x - 1, y, East_dir)) {
            return true;
        }
        return false;
    }
    // Mark x,y part of solution path.
    maze[y][x] = '.';
    find_enterence = true;
    // If find_path North of x,y is true, return true.
    if ( ifrom_dir != North_dir && find_path(x, y - 1, South_dir) == true ) return true;
    // If find_path East of x,y is true, return true.
    if ( ifrom_dir != East_dir && find_path(x + 1, y, West_dir) == true ) return true;
    // If find_path South of x,y is true, return true.
    if ( ifrom_dir != South_dir && find_path(x, y + 1, North_dir) == true ) return true;
    // If find_path West of x,y is true, return true.
    if ( ifrom_dir != West_dir && find_path(x - 1, y, East_dir) == true ) return true;
    // Unmark x,y as part of solution path.
    maze[y][x] = '+';
    return false;
}