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

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("Failed\n");

    display_maze();

    return 0;
}



void display_maze()
{
    int i;

    printf("MAZE:\n");
    for ( i = 0; i < NROWS; i++ )
    printf("%.*s\n", 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;
}

对于这个迷宫迭代，它运行良好。输出打印 "Success" 并显示从 'S' 到 'E'.

的路径

但是，我是否应该像这样移动 'S' 的位置：

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

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

另一个问题 - 如您所见，我在我的 .cpp 文件中实现了一个示例迷宫。但是，我的最终目标是从 .txt 文件流式传输迷宫。因此，每个迷宫将具有不同的维度。那么使用向量而不是字符数组对我来说更有意义吗？

Answer 1

对于迷宫，

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

当您使用包含 X 的参数 (0,0) 调用 find_path() 时。所以

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

在 find_path() 中执行，其中 returns 为假。所以输出是 Failed.

您必须找到 '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("Failed\n");

    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;
}

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

My recursive maze solver does not recognize start position correctly

c++

recursion

maze