數(shù)據(jù)結(jié)構(gòu)與算法之迷宮

1、WORD格式數(shù)據(jù)構(gòu)造預(yù)算法迷宮問(wèn)題*工業(yè)大學(xué)金字塔的小蝸牛一、問(wèn)題描述：編寫(xiě)一個(gè)程序：隨機(jī)生成一個(gè) 20 x 20 的迷宮，并找到一條從入口到出口的路線。要求： (1)“迷宮大小可變，模式隨機(jī)。(2)迷宮沒(méi)有通路時(shí)，給出警告；有通路時(shí)，任給一條具體路徑。(3)分析算法的效率。二、算法根本思想：通過(guò)產(chǎn)生隨機(jī)數(shù)的方式生成一個(gè)只含 0 和 1 的二維數(shù)組， 用這個(gè)二維數(shù)組來(lái)表示迷宮，其中數(shù)字 1 表示通路，數(shù)字 0 表示圍墻。設(shè)定好迷宮的入口和出口，采用遞歸的方法找到一條走出迷宮的路線圖， 數(shù)組 my_maze存有正尋找的路線圖，在找路線圖的運(yùn)行過(guò)程中沒(méi)有出口的路線圖即被后來(lái)的路線覆蓋， 直到找到能

2、走出迷宮的路線圖，然后將 my_maze中的元素賦給 target_maze 。最終將路線圖 target_maze 打印出來(lái)。三、主要數(shù)據(jù)構(gòu)造編程環(huán)境：code blocks：1、二維數(shù)組一個(gè)表示迷宮的二維數(shù)組mazeij，相關(guān)操作有：(1) 建立二維數(shù)組，賦初值。(2) 數(shù)組以指針形式在各函數(shù)中傳遞。(3) 改變數(shù)組中某個(gè)元素的值。2、指針運(yùn)算函數(shù) move_to、print_maze1 、print_maze2 都含有指針作為函數(shù)中的變量進(jìn)展調(diào)用。3、遞歸運(yùn)算在尋找迷宮路徑的時(shí)候，用到了遞歸運(yùn)算。在程序中即從一個(gè)點(diǎn)搜尋下一個(gè)點(diǎn)的反復(fù)過(guò)程中不斷調(diào)用 move_to 函數(shù)自身，最終尋找到走出

3、迷宮的路徑。四、主要函數(shù)功能：1、produce_maze()函數(shù)功能：隨機(jī)生成一個(gè)20 x 20 的二維迷宮。2、move_to(int _i,int _j, int (*in_maze)MAX_COL, int count)函數(shù)功能：采用遞歸思想找到一條走出迷宮的路徑。3、print_maze1(int (*maze)MAX_COL)函數(shù)功能：打印出生成的迷宮圖案。4、print_maze2(int (*maze1)MAX_COL,int (*maze2)MAX_COL)函數(shù)功能：打印出附有路徑的迷宮圖案。專(zhuān)業(yè)資料整理WORD格式五、一個(gè)算例：專(zhuān)業(yè)資料整理WORD格式程序運(yùn)行的一個(gè)結(jié)果如下

4、所示：專(zhuān)業(yè)資料整理WORD格式專(zhuān)業(yè)資料整理WORD格式專(zhuān)業(yè)資料整理WORD格式專(zhuān)業(yè)資料整理WORD格式六、算法分析：程序運(yùn)行時(shí)間主要在于不斷的由一個(gè)點(diǎn)往下尋找另一個(gè)點(diǎn)的過(guò)程， 對(duì)于一個(gè) m*n 的迷宮來(lái)說(shuō)，其時(shí)間復(fù)雜度不會(huì)超過(guò) m*n4. 但實(shí)際運(yùn)行過(guò)程中會(huì)節(jié)約很多時(shí)間，因?yàn)槌绦驅(qū)ふ衣窂綍r(shí)以向下、向右為先。在空間占用上， 因?yàn)楸４鎸ふ衣窂降?my_maze采用不斷覆蓋的方式， 只將最終成功的路線賦給 target_maze ，所以在一定程度上節(jié)省了運(yùn)行與存儲(chǔ)空間。附錄： C語(yǔ)言源代碼#include #include #include #include /*定義迷宮的大小 */#define

5、MAX_COL 9#define MAX_ROW 9#define TRUE 1#define FALSE 0#defineIS_USABLE(a, b) (a = 0 & a = 0 & b MAX_COL)& mazeab & (!my_mazeab) static int mazeMAX_ROWMAX_COL; static int target_mazeMAX_ROWMAX_COL;static void init_maze();static int move_to(int i, int j, int (*maze)MAX_COL, int count); static void pr

6、int_maze(int (*maze)MAX_COL);static void init_maze()int i, j;srand(unsigned) time(NULL);for (i = 0; i MAX_ROW; i+)for (j = 0; j MAX_COL; j+)mazeij = (int) (rand() % 2);專(zhuān)業(yè)資料整理WORD格式maze10 = 1; /*設(shè)定迷宮入口*/專(zhuān)業(yè)資料整理WORD格式mazeMAX_ROW - 1MAX_COL - 2 = 1; /*設(shè)定迷宮出口 */專(zhuān)業(yè)資料整理WORD格式static int move_to(int _i,int _

7、j, int (*in_maze)MAX_COL, int count)int my_mazeMAX_ROWMAX_COL, i, j;if (!in_maze)for (i = 0; i MAX_ROW; i+)for (j = 0; j MAX_COL; j+)my_mazeij = 0;elsefor (i = 0; i MAX_ROW; i+)for (j = 0; j MAX_COL; j+)my_mazeij = in_mazeij;my_maze_i_j = count;/* reach the end point */if (_i = MAX_ROW - 1 & _j = MA

8、X_COL - 2)for (i = 0; i MAX_ROW; i+)for (j = 0; j MAX_COL; j+)target_mazeij = my_mazeij;return TRUE;if (IS_USABLE(_i - 1, _j)if (move_to(_i - 1, _j, my_maze, count + 1)return TRUE;if (IS_USABLE(_i + 1, _j)if (move_to(_i + 1, _j, my_maze, count + 1)return TRUE;if (IS_USABLE(_i, _j - 1)專(zhuān)業(yè)資料整理WORD格式if

9、(move_to(_i, _j - 1, my_maze, count + 1)return TRUE;if (IS_USABLE(_i, _j + 1)if (move_to(_i, _j + 1, my_maze, count + 1)return TRUE;return FALSE;static void print_maze(int (*maze)MAX_COL)int i, j;printf( );for (i = 0; i MAX_ROW; i+)for (j = 0; j MAX_COL; j+)if (mazeij != 0)if (mazeij10)printf(%d , mazeij);elseprintf(%d , mazeij);elseprintf();printf( n );int main()while (1)init_maze();printf(生成的