曲径通幽论坛

标题: 递归方法走迷宫 [打印本页]

---

作者: beyes    时间: 2009-9-13 22:28
标题: 递归方法走迷宫
除了用栈的方法可以走迷宫外，用递归也可以实现。假设迷宫数组为：

int maze [7][10] = {        /*迷宫数组*/
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 0, 1, 0, 1, 0, 0, 0, 0, 1,
        1, 0, 1, 0, 1, 0, 1, 1, 0, 1,
        1, 0, 1, 0, 1, 1, 1, 0, 0, 1,
        1, 0, 1, 0, 0, 0, 0, 0, 1, 1,
        1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

测试代码：

#include <stdio.h>

int maze [7][10] = {            /*迷宫数组*/
                1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                   1, 0, 1, 0, 1, 0, 0, 0, 0, 1,
                   1, 0, 1, 0, 1, 0, 1, 1, 0, 1,
                1, 0, 1, 0, 1, 1, 1, 0, 0, 1,
                1, 0, 1, 0, 0, 0, 0, 0, 1, 1,
                1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
                1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

int find_path (int x, int y)
{
    if (x == 1 && y == 1) {        /*是否是迷宫出口*/
        maze[x][y] = 2;        /*记录最后走过的路径*/
        return (1);
    } else if (maze[x][y] == 0) {    /*是不是可以走*/
        maze[x][y] = 2;        /*记录已走过的路径*/
         
        if ((    find_path (x - 1, y) +        /*递归往上*/
                 find_path (x + 1, y) +      /*递归往下*/
                 find_path (x, y - 1) +      /*递归往左*/
                 find_path (x, y + 1)) > 0)     /*递归往右*/
            return (1);
        else {
            maze[x][y] = 0;        /*此路不通,取消记号*/
            return (0);
        }
   
    } else return (0);
}
       

int main ()
{
    int i, j;
   
    find_path (5, 8);
    printf ("迷宫的路径如下图所示:\n");
    for (i = 1; i < 6; i++) {
        for (j = 1; j < 9; j++)
            printf ("%d", maze[i][j]);    /*输出各坐标*/
        printf ("\n");
    }

    return (0);
}

运行及输出：

beyes@linux-beyes:~/C/structer/recursion> ./maze.exe
迷宫的路径如下图所示:
21010000
21010110
21011100
21222221
22211122

程序说明：
使用递归算法，会遍历到每个路径座标。从当前坐标寻找路径时的测试顺序是：上、下、左、右。

从当前坐标出发去测试它周围四个方向的坐标时，会用到 4 个 find_path() 函数。find_path() 函数含有两个参数，分别是坐标值。假如用 find_path() 测试坐标值(maze[x][y]) 是否为0，如果是 0 ，则表示此路可走，同时为对这个坐标值改为 2 。像这种遇到 0 值坐标的情况，会衍生出 4 个 find_path() 函数，这就是一种递归的表现 --- 层层深入，最后返回。假如 find_path() 测试到四周的坐标都走不通时，它会进行回溯。由于 find_path() 在测试时，对无法通行的坐标(包括坐标值为1和走过来的坐标值为2的坐标)，会返回 0 值， 所以四周都无法再前行时，4 个 find_path() 函数 的和为 0 。这样，就需要回溯，在回溯前对将当前坐标值从 2 改为 0 ，做这标记是为了在最后输出路径时不致于视觉上的混淆。假如说，最后找到了正确路径，那么在正确路径上的 find_path() 返回时返回的值是 1 ，所以 4 个 find_path() 函数之和会 > 0 。

---

欢迎光临 曲径通幽论坛 (http://www.groad.net/bbs/)

Powered by Discuz! X3.2