定義一個二維數組： 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)

總結

以上是生活随笔為你收集整理的用深度优先搜索解迷宫问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。