找到一个迷宫路径成本 [英] Finding a cost for a maze path

问题描述

我有这个迷宫：

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

在＃符号墙壁迷宫。

The "#" symbols are walls in the maze.

迷宫的+的区域是从进入点迷宫可达区域，而 - 的迷宫区域是从进入点可达。进入点位于迷宫的顶部。

The "+" regions of the maze are reachable regions of the maze from the entry point, and the "-" region of the maze are unreachable from the entry point. The entry point is located at the top of the maze.

我想现在要做的就是剧情迷宫可到达地区的成本，这将是这样的：

What I would like to do now is plot a cost of the reachable regions in the maze, which will look like this:

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

这表明，该迷宫具有10从条目费用退出。

This shows that the maze has a cost of 10 from entry to exit.

迷宫向上顶存储在二维数组，我用递归解决可达区域。我如何用我的递归函数，它看起来像这样标注的路径成本：

The maze up top is stored in a 2d array and I used recursion to solve the reachable zones. How can I label costs of the paths using my recursive function, which looks like this:

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

有关的第一迷宫，我在迷宫的顶部用这个递归函数，并且它洪水填充所有可达细胞用+。

For the first maze, I used this recursive function at the top of the maze, and it flood filled all the reachable cells with "+".

是否有任何建议，我该怎么做类似这样的，但东西的路径开销来代替。我只是在寻找一些例子或建议，我怎么可能去做。我如何能去实现第二个迷宫的例子任何帮助将是有益的。

Are there any suggestions as to how I can do something similar to this but with the path costs instead. I'm just looking for some examples or suggestions as to how I might go about it. Any help on how I can go about achieving the second maze example would be helpful.

推荐答案

传递一个额外的参数是路径成本为止。

Pass an extra parameter that is the path cost so far.

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

每个迷宫位置获得一个附加属性，。成本，你更新你洪水填充迷宫。初始化到MAXINT作为标记的成本。
例如，

Each maze location gets an additional attribute, .cost, which you update as you flood-fill the maze. Initialize the cost to MAXINT as a marker. For instance,

    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

在任何情况下，你现在有成本每平方米。显示，当您转储迷宫屏幕所需。

In any case, you now have the cost to each square. Display as desired when you dump the maze to the screen.

这篇关于找到一个迷宫路径成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！