用深度优先搜索解迷宫问题

定义一个二维数组： int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0, };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。程序如下：

[cpp] view plaincopy

//By LYLtim  

  

#include<stdio.h>  

  

const int di[4] = {0,1,0,-1},  

          dj[4] = {1,0,-1,0};  

  

unsigned maze[5][5] = {  

    2, 1, 0, 0, 0,  

    0, 1, 0, 1, 0,  

    0, 0, 0, 0, 0,  

    0, 1, 1, 1, 0,  

    0, 0, 0, 1, 0},  

    ip = 0;  

  

struct { int i, j; } path[23] = {0};  

  

void print_maze(void)  

{  

    int i, j;  

    for (i = 0; i < 5; i++) {  

        for (j = 0; j < 5; j++)  

            printf("%d ", maze[i][j]);  

        putchar('\n');  

    }  

    printf("*********\n");  

}  

  

void print_path(void)  

{  

    int i = 0;  

    printf("(0,0)");  

    for (i = 0; i < ip; i++)  

        printf("->(%d,%d)", path[i].i, path[i].j);  

    exit(0);  

}  

  

void try(int i, int j)  

{  

    int k;  

    for (k = 0; k < 4; k++)  

        if (i + di[k] >= 0 && i + di[k] <5  

            && j + dj[k] >= 0 && j + dj[k] < 5  

            && maze[i + di[k]][j + dj[k]] == 0) {  

                maze[i + di[k]][j + dj[k]] = 2;  

                path[ip++].i = i + di[k]; path[ip].j = j + dj[k];  

                print_maze();  

                if (i + di[k] == 4 && j + dj[k] == 4)  

                    print_path();  

                else  

                    try(i + di[k], j + dj[k]);  

                maze[i+di[k]][j+dj[k]] = 0;  

                path[--ip].i = 0; path[ip].j = 0;  

        }  

}  

          

  

int main(void)  

{  

    try(0, 0);  

    return 0;  

}  

运行结果如下：

2 1 0 0 0 2 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 0 0 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 0 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 2 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 2 2 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 2 2 0 1 1 1 2 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 2 2 0 1 1 1 2 0 0 0 1 2 ********* (0,0)->(1,0)->(2,0)->(2,0)->(2,1)->(2,2)->(2,3)->(3,4)->(4,4)

总结

以上是生活随笔为你收集整理的用深度优先搜索解迷宫问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。