寻找迷宫路径的成本

Question

我有这个迷宫：

    ##++##############
    ##++++++++++++++##
    ########++########
    ##++++++++##----##
    ##++########--####

“#”符号是迷宫中的墙。

迷宫的“+”区域是从入口点可达的迷宫区域，“-”区域是从入口点无法到达的区域。入口点位于迷宫的顶部。

我现在想做的是绘制迷宫中可到达区域的成本，如下所示：

    ##00##############
    ##++02++04++06++##
    ########++########
    ##++08++06##----##
    ##10########--####

这表明迷宫从入口到出口的成本为10。

迷宫顶部存储在一个二维数组中，我使用递归来解决可达区域。如何使用我的递归函数标记路径成本，如下所示：

    void
    flood_fill(m_t * maze, int row, int col) {
        // If row,col is outside maze
        if ( row < 0 || row >= maze->height || col < 0 || col >= maze->width) return;
        // If row,col is not open
        if (maze->M[row][col].type != '.') return;

        // Mark row,col as part of path.
        maze->M[row][col].type = '+';

        // Go LEFT
        flood_fill(maze, row, col - 1);
        // Go DOWN
        flood_fill(maze, row + 1, col);
        // Go RIGHT
        flood_fill(maze, row, col + 1);
        // Go UP
        flood_fill(maze, row - 1, col);

        return;
    }

对于第一个迷宫，我在迷宫的顶部使用了这个递归函数，它用“+”填充了所有可到达的单元格。

是否有任何关于如何使用路径成本来做类似的事情的建议。我只是在寻找一些关于我如何去做的例子或建议。关于如何实现第二个迷宫示例的任何帮助都会有所帮助。

Answer 1

传递一个额外的参数，即到目前为止的路径成本。

flood_fill(m_t * maze, int row, int col, int cost)

每个迷宫位置都有一个额外的属性，.cost，您可以在填满迷宫时更新该属性。将成本初始化为 MAXINT 作为标记。例如，

    if (maze->M[row][col].cost > cost)
      maze->M[row][col].cost = cost

    // Go LEFT
    flood_fill(maze, row, col - 1, cost+1);
    // repeat for the other 3 directions

无论如何，您现在有了每个方格的成本。当你将迷宫转储到屏幕上时，根据需要显示。

寻找迷宫路径的成本

Finding a cost for a maze path

c

recursion

flood-fill