經典演演算法大全51例——5&6.老鼠走迷官
2020-10-02 11:00:07
經典演演算法大全51例——5&6.老鼠走迷官
演演算法目錄合集
地址
說明
該地址指向所有由本人自己所經歷的演演算法習題(也有可能僅僅是一個入門的案例或者是經典案例)，僅僅為我做過而且比較有意思的，也許還會有一些我自己想出來的，出於興趣寫在這裡,具體格式我會在下面列明，總目錄也會在這裡出現，方便查閱以及自己進行復習回顧。
題目以及個人題解
說明
這個在原文中是兩個題,我把他們綜合一下，作為一個題展現給大家，為了不水貼嘛，看看我有多好啊🤗🤗🤗🤗哈哈哈。
題目
我們在二維陣列中使用2表示迷宮牆壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。
思考：由於迷宮的設計，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？
例如：{{2, 2, 2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 0, 0, 2}, {2, 0, 2, 2, 0, 2, 2, 0, 2}, {2, 0, 2, 0, 0, 2, 0, 0, 2}, {2, 0, 2, 0, 2, 0, 2, 0, 2}, {2, 0, 0, 0, 0, 0, 2, 0, 2}, {2, 2, 0, 2, 2, 0, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 0, 0, 2}, {2, 2, 2, 2, 2, 2, 2, 2, 2}}
特別說明
第二個問題（思考部分）其實在《經典演演算法大全51例》裡面是第六道題，我看型別太過相似了，簡直就是一道題，所以我合在一起了
原理分析
其實做這題的思路倒是非常簡單的，大家想一想，小時候自己有沒有玩兒過鏡子迷宮，就算沒有，也總玩兒紙上迷宮吧，想一想被迷宮支配的恐懼！
大家回憶一下，面對迷宮是怎麼操作的？有人就會懟我了「廢話，還能咋咋操作，當然是哪兒有路往哪兒走啦」，話說的很對，我接受被懟，那麼你怎麼知道哪兒有路呢？有人又該懟我了「那你要眼睛出氣兒的啊」，嗯，我還接受，下面我又要問了：「題目中的老鼠，你怎麼給他賦予一雙智慧的眼睛呢？」
其實很簡單，就像第一句懟我的話：哪兒有路往哪兒走，那麼在程式中怎麼讓老鼠擁有眼睛呢？那很簡單，假如現在老鼠隨便站一個位置（這個位置肯定是0啊，別跟我犟，哼哼😕），那麼我們就去看看這個位置的上下左右是不是可以通行（0是空地，2是牆壁），如果是0，那麼就可以讓老鼠到這兒，並且再次進行是否可以通行的判斷，那麼問題來了，萬一這隻老鼠反覆橫跳😕怎麼辦?就像這種矩陣：
其實避免這種情況的方法題目裡也已經給我們了：使用1來表示老鼠的行走路徑。那麼我們只需要判斷周圍是不是0就可以了，這樣就可以在最後顯示出來路徑了。
問題①
原理
我們先來做第一問：只尋找一條路：
為了方便展示，我們先畫出來地圖原圖來把矩陣進行展示，然後呼叫老鼠行走的方法，最後繪製帶有路徑的地圖，這就是主方法：
//列印地圖
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路
case 0:
System.out.print(" ");
break;
//代表牆
case 2:
System.out.print("📦");
break;
default:
break;
}
}
System.out.println();
}
//開始尋找
seekOnce(maze, startRow, startRank);
System.out.println("=====================");
//列印路徑
if (success) {
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路
case 0:
System.out.print(" ");
break;
//代表老鼠走的路
case 1:
System.out.print("🐾");
break;
//代表牆
case 2:
System.out.print("📦");
break;
default:
break;
}
}
System.out.println();
}
} else {
System.out.println("找不到出口");
}
}
而對於老鼠行走的方法，我們在原理分析的時候已經分析過了，首先把老鼠走過的位置從0變成1（🐶：「這是不是和我撒尿一個道理？」，🙄：「我呸！」），然後繼續找上下左右哪裡有0，有0就過去，把他變成1（🎃感覺怪怪的？？🎃）：
maze[i][j] = 1;
if (!success && maze[i][j + 1] == 0) {
seekOnce(maze, i, j + 1);
}
if (!success && maze[i + 1][j] == 0) {
seekOnce(maze, i + 1, j);
}
if (!success && maze[i][j - 1] == 0) {
seekOnce(maze, i, j - 1);
}
if (!success && maze[i - 1][j] == 0) {
seekOnce(maze, i - 1, j);
}
沒0就不用繼續討論了；假如某條分支A，呼叫了四個方向，發現四周不是走過的路（1）就是牆（2），那麼就再把這條分支變回0就行了：
if (!success) {
maze[i][j] = 0;
}
一直等老鼠到達了我們指定的終點，那麼就把標識是否完成迷宮的識別符號變成true，那麼就成功了，如果遍歷完了所有格子，我們的小老鼠依舊沒有到達指定的重點，那麼識別符號還是false，最後我們只需要將識別符號返回，就可以判斷是否有這麼一條路徑可以讓老鼠達到終點了：
if (success) {
//列印地圖
} else {
System.out.println("找不到出口");
}
可以注意一下，因為結束的條件有兩種，一個是找完所有的路，然後發現沒有出口，結束了整個流程，另一種就是已經找到了重點，那這個時候何必繼續呼叫方法呢，所以每一條我都增加了判斷條件：
if (success)
程式碼實現——Java
package com.interest;
/**
* com.interest
*
* @author g55zhw
* @create 2020-09-30-20-54
*/
public class MouseFindOnce {
static int startRow = 1, startRank = 1;
static int endRow = 7, endRank = 7;
static int count = 1;
static boolean success = false;
static int[][] maze = new int[][]{
{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}
};
public static void main(String[] args) {
//列印地圖
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路
case 0:
System.out.print(" ");
break;
//代表牆
case 2:
System.out.print("📦");
break;
default:
break;
}
}
System.out.println();
}
//開始尋找
seekOnce(maze, startRow, startRank);
System.out.println("=====================");
//列印路徑
if (success) {
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路
case 0:
System.out.print(" ");
break;
//代表老鼠走的路
case 1:
System.out.print("🐾");
break;
//代表牆
case 2:
System.out.print("📦");
break;
default:
break;
}
}
System.out.println();
}
} else {
System.out.println("找不到出口");
}
}
static boolean seekOnce(int[][] maze, int i, int j) {
System.out.println("(" + i + "," + j + ")" + count);
count++;
maze[i][j] = 1;
if (i == endRow && j == endRank) {
success = true;
}
if (!success && maze[i][j + 1] == 0) {
seekOnce(maze, i, j + 1);
}
if (!success && maze[i + 1][j] == 0) {
seekOnce(maze, i + 1, j);
}
if (!success && maze[i][j - 1] == 0) {
seekOnce(maze, i, j - 1);
}
if (!success && maze[i - 1][j] == 0) {
seekOnce(maze, i - 1, j);
}
if (!success) {
maze[i][j] = 0;
}
return success;
}
}
結果演示
由於字元的間距問題,空格在這兒顯示會有點兒問題,大家勉強能看~~~
📦📦📦📦📦📦📦📦📦
📦 📦
📦 📦📦 📦📦 📦
📦 📦 📦 📦
📦 📦 📦 📦 📦
📦 📦 📦
📦📦 📦📦 📦📦📦
📦 📦
📦📦📦📦📦📦📦📦📦
(1,1)1
(1,2)2
(1,3)3
(1,4)4
(1,5)5
(1,6)6
(1,7)7
(2,7)8
(3,7)9
(4,7)10
(5,7)11
(3,6)12
(2,4)13
(3,4)14
(3,3)15
(4,3)16
(5,3)17
(5,4)18
(5,5)19
(6,5)20
(7,5)21
(7,6)22
(7,7)23
📦📦📦📦📦📦📦📦📦
📦🐾🐾🐾🐾 📦
📦 📦📦🐾📦📦 📦
📦 📦🐾🐾📦 📦
📦 📦🐾📦 📦 📦
📦 🐾🐾🐾📦 📦
📦📦 📦📦🐾📦📦📦
📦 🐾🐾🐾📦
📦📦📦📦📦📦📦📦📦
大家可以看到，除了列印了地圖我還增加了一條列印內容，那就是現在進行的地點以及第幾次呼叫方法，大家把上下左右的順序換一換，這個值也會發生變化，比如先判斷向下走：
if (!success && maze[i + 1][j] == 0) {
seekOnce(maze, i + 1, j);
}
if (!success && maze[i][j + 1] == 0) {
seekOnce(maze, i, j + 1);
}
if (!success && maze[i - 1][j] == 0) {
seekOnce(maze, i - 1, j);
}
if (!success && maze[i][j - 1] == 0) {
seekOnce(maze, i, j - 1);
}
這樣的話，那路線就是向下為主了，大家可以自己試一試。
問題②
原理
第二個問題其實經過了第一題的洗禮，大家應該很容易就接受了，我就不一步一步說步驟了，說一個大致的過程，然後在程式碼裡放一串「神祕程式碼」，大家自然就可以理解了：
①首先把成功識別符號去掉，這樣才能讓老鼠就算成功到達了一次重點也不至於終結整個方法；
重要：
②（這段解釋同樣實用於問題一，但是在這裡更容易理解，我才放在這兒了）我增加了這麼一條語句來幫助大家理解，其實並不是老鼠在走，走到終點或者走不動了才回頭，而是我們認為地去調方法，因為如果真的是老鼠在走，那麼就不會一下子執行100多次才會終止了，真正的情況是：我們每次呼叫方法的時候，都是相當於施行了一次「影分身」，假如老鼠站的位置現在上左不能走，那麼我們就讓他去下和右，這樣就分了一次身；去右邊那個假如又遇到分叉了，再分身……剩下的就是和問題一的執行類似了，有路到終點，那麼1就是1，0就是0，如果這個分支到不了終點，那麼0還是0，1也是0；
System.out.println("========第" + count + "次呼叫seekForever方法========");
count++;
程式碼實現——Java
package com.interest;
/**
* com.interest
*
* @author g55zhw
* @create 2020-09-30-21-14
*/
public class MouseFindAll {
static int startRow = 1, startRank = 1;
static int endRow = 7, endRank = 7;
static int count = 1;
static int[][] mazeTitle = new int[][]{
{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}
};
public static void main(String[] args) {
seekForever(mazeTitle, startRow, startRank);
}
static void seekForever(int[][] maze, int i, int j) {
//首先賦值為1,表示這塊地板我已經來了
maze[i][j] = 1;
System.out.println("========第" + count + "次呼叫seekForever方法========");
count++;
//列印地圖
if (i == endRow && j == endRank) {
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路
case 0:
System.out.print(" ");
break;
//代表老鼠走的路
case 1:
System.out.print("🐾");
break;
//代表牆
case 2:
System.out.print("📦");
break;
default:
break;
}
}
System.out.println();
}
}else {
System.out.println("還沒有到終點");
}
//以下四個方向,有任何一個方向是路(0)的話,就可以通行(呼叫seekForever方法);
if (maze[i][j + 1] == 0) {
seekForever(maze, i, j + 1);
}
if (maze[i + 1][j] == 0) {
seekForever(maze, i + 1, j);
}
if (maze[i - 1][j] == 0) {
seekForever(maze, i - 1, j);
}
if (maze[i][j - 1] == 0) {
seekForever(maze, i, j - 1);
}
//四個方向都沒有路的話就把已經踩過的地板換回0,假裝沒來過→_→
maze[i][j] = 0;
}
}
結果演示
========第1次呼叫seekForever方法========
還沒有到終點
========第2次呼叫seekForever方法========
還沒有到終點
========第3次呼叫seekForever方法========
還沒有到終點
========第4次呼叫seekForever方法========
還沒有到終點
========第5次呼叫seekForever方法========
還沒有到終點
========第6次呼叫seekForever方法========
還沒有到終點
========第7次呼叫seekForever方法========
還沒有到終點
========第8次呼叫seekForever方法========
還沒有到終點
========第9次呼叫seekForever方法========
還沒有到終點
========第10次呼叫seekForever方法========
還沒有到終點
========第11次呼叫seekForever方法========
還沒有到終點
========第12次呼叫seekForever方法========
還沒有到終點
========第13次呼叫seekForever方法========
還沒有到終點
========第14次呼叫seekForever方法========
還沒有到終點
========第15次呼叫seekForever方法========
還沒有到終點
========第16次呼叫seekForever方法========
還沒有到終點
========第17次呼叫seekForever方法========
還沒有到終點
========第18次呼叫seekForever方法========
還沒有到終點
========第19次呼叫seekForever方法========
還沒有到終點
========第20次呼叫seekForever方法========
還沒有到終點
========第21次呼叫seekForever方法========
還沒有到終點
========第22次呼叫seekForever方法========
還沒有到終點
========第23次呼叫seekForever方法========
📦📦📦📦📦📦📦📦📦
📦🐾🐾🐾🐾 📦
📦 📦📦🐾📦📦 📦
📦 📦🐾🐾📦 📦
📦 📦🐾📦 📦 📦
📦 🐾🐾🐾📦 📦
📦📦 📦📦🐾📦📦📦
📦 🐾🐾🐾📦
📦📦📦📦📦📦📦📦📦
========第24次呼叫seekForever方法========
還沒有到終點
========第25次呼叫seekForever方法========
還沒有到終點
========第26次呼叫seekForever方法========
還沒有到終點
========第27次呼叫seekForever方法========
還沒有到終點
========第28次呼叫seekForever方法========
還沒有到終點
========第29次呼叫seekForever方法========
還沒有到終點
========第30次呼叫seekForever方法========
還沒有到終點
========第31次呼叫seekForever方法========
還沒有到終點
========第32次呼叫seekForever方法========
還沒有到終點
========第33次呼叫seekForever方法========
還沒有到終點
========第34次呼叫seekForever方法========
還沒有到終點
========第35次呼叫seekForever方法========
還沒有到終點
========第36次呼叫seekForever方法========
還沒有到終點
========第37次呼叫seekForever方法========
還沒有到終點
========第38次呼叫seekForever方法========
還沒有到終點
========第39次呼叫seekForever方法========
還沒有到終點
========第40次呼叫seekForever方法========
還沒有到終點
========第41次呼叫seekForever方法========
還沒有到終點
========第42次呼叫seekForever方法========
📦📦📦📦📦📦📦📦📦
📦🐾🐾🐾🐾 📦
📦 📦📦🐾📦📦 📦
📦 📦🐾🐾📦 📦
📦 📦🐾📦 📦 📦
📦 🐾🐾 📦 📦
📦📦🐾📦📦 📦📦📦
📦 🐾🐾🐾🐾🐾🐾📦
📦📦📦📦📦📦📦📦📦
========第43次呼叫seekForever方法========
還沒有到終點
========第44次呼叫seekForever方法========
還沒有到終點
========第45次呼叫seekForever方法========
還沒有到終點
========第46次呼叫seekForever方法========
還沒有到終點
========第47次呼叫seekForever方法========
還沒有到終點
========第48次呼叫seekForever方法========
還沒有到終點
========第49次呼叫seekForever方法========
還沒有到終點
========第50次呼叫seekForever方法========
還沒有到終點
========第51次呼叫seekForever方法========
還沒有到終點
========第52次呼叫seekForever方法========
還沒有到終點
========第53次呼叫seekForever方法========
還沒有到終點
========第54次呼叫seekForever方法========
還沒有到終點
========第55次呼叫seekForever方法========
還沒有到終點
========第56次呼叫seekForever方法========
還沒有到終點
========第57次呼叫seekForever方法========
還沒有到終點
========第58次呼叫seekForever方法========
還沒有到終點
========第59次呼叫seekForever方法========
還沒有到終點
========第60次呼叫seekForever方法========
還沒有到終點
========第61次呼叫seekForever方法========
還沒有到終點
========第62次呼叫seekForever方法========
還沒有到終點
========第63次呼叫seekForever方法========
📦📦📦📦📦📦📦📦📦
📦🐾 📦
📦🐾📦📦 📦📦 📦
📦🐾📦 📦 📦
📦🐾📦 📦 📦 📦
📦🐾🐾🐾🐾🐾📦 📦
📦📦 📦📦🐾📦📦📦
📦 🐾🐾🐾📦
📦📦📦📦📦📦📦📦📦
========第64次呼叫seekForever方法========
還沒有到終點
========第65次呼叫seekForever方法========
還沒有到終點
========第66次呼叫seekForever方法========
還沒有到終點
========第67次呼叫seekForever方法========
還沒有到終點
========第68次呼叫seekForever方法========
還沒有到終點
========第69次呼叫seekForever方法========
還沒有到終點
========第70次呼叫seekForever方法========
還沒有到終點
========第71次呼叫seekForever方法========
還沒有到終點
========第72次呼叫seekForever方法========
還沒有到終點
========第73次呼叫seekForever方法========
還沒有到終點
========第74次呼叫seekForever方法========
還沒有到終點
========第75次呼叫seekForever方法========
還沒有到終點
========第76次呼叫seekForever方法========
還沒有到終點
========第77次呼叫seekForever方法========
還沒有到終點
========第78次呼叫seekForever方法========
還沒有到終點
========第79次呼叫seekForever方法========
還沒有到終點
========第80次呼叫seekForever方法========
還沒有到終點
========第81次呼叫seekForever方法========
還沒有到終點
========第82次呼叫seekForever方法========
還沒有到終點
========第83次呼叫seekForever方法========
還沒有到終點
========第84次呼叫seekForever方法========
還沒有到終點
========第85次呼叫seekForever方法========
還沒有到終點
========第86次呼叫seekForever方法========
還沒有到終點
========第87次呼叫seekForever方法========
還沒有到終點
========第88次呼叫seekForever方法========
還沒有到終點
========第89次呼叫seekForever方法========
還沒有到終點
========第90次呼叫seekForever方法========
還沒有到終點
========第91次呼叫seekForever方法========
📦📦📦📦📦📦📦📦📦
📦🐾 📦
📦🐾📦📦 📦📦 📦
📦🐾📦 📦 📦
📦🐾📦 📦 📦 📦
📦🐾🐾 📦 📦
📦📦🐾📦📦 📦📦📦
📦 🐾🐾🐾🐾🐾🐾📦
📦📦📦📦📦📦📦📦📦
========第92次呼叫seekForever方法========
還沒有到終點
========第93次呼叫seekForever方法========
還沒有到終點
========第94次呼叫seekForever方法========
還沒有到終點
========第95次呼叫seekForever方法========
還沒有到終點
========第96次呼叫seekForever方法========
還沒有到終點
========第97次呼叫seekForever方法========
還沒有到終點
========第98次呼叫seekForever方法========
還沒有到終點
========第99次呼叫seekForever方法========
還沒有到終點
========第100次呼叫seekForever方法========
還沒有到終點
========第101次呼叫seekForever方法========
還沒有到終點
========第102次呼叫seekForever方法========
還沒有到終點
========第103次呼叫seekForever方法========
還沒有到終點
========第104次呼叫seekForever方法========
還沒有到終點
========第105次呼叫seekForever方法========
還沒有到終點
========第106次呼叫seekForever方法========
還沒有到終點
========第107次呼叫seekForever方法========
還沒有到終點
========第108次呼叫seekForever方法========
還沒有到終點
========第109次呼叫seekForever方法========
還沒有到終點
========第110次呼叫seekForever方法========
還沒有到終點
========第111次呼叫seekForever方法========
還沒有到終點
========第112次呼叫seekForever方法========
還沒有到終點
相關題目其他變形：
1.地下城遊戲（來源：力扣LeetCode）
這個力扣的地下城遊戲問題是一個提升版，大家看了首先第一個意識就是可以這麼去分析，其實這個就是動態規劃了，我目前還沒有整理動態規劃的相關知識，演演算法的基礎合集估計以後會出，前提是我還沒有被產品經理累死，哈哈哈。
大家自己看看把，我的專欄也收錄了，連結給你們，自己去看，可以練練手，地下城遊戲(困難難度)——萬能的遞迴與動態分析。
哈哈，炫耀炫耀。
其他的變形我也不給了，十一了，明天就要出去浪了，懶得自己想了🙄🙄，哈哈哈，其實相關類似的題在力扣領釦都挺多的，大家可以自己去看看，很好玩兒的。
官方題解
老鼠走迷宮（一）
解法
老鼠的走法有上、左、下、右四個方向，在每前進一格之後就選一個方向前進，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞迴的基本題，請直接看程式應就可以理解。
程式碼——C語言
#include <stdio.h>
#include <stdlib.h>
int visit(int, int);
int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}};
int startI = 1, startJ = 1;
// 入口
int endI = 5, endJ = 5;
// 出口
int success = 0;
int main(void) {
int i, j;
printf("顯示迷宮：\n");
for (i = 0; i < 7; i++) {
for (j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█"); else
printf(" ");
printf("\n");
}
if(visit(startI, startJ) == 0)
printf("\n沒有找到出口！\n"); else {
printf("\n顯示路徑：\n");
for (i = 0; i < 7; i++) {
for (j = 0; j < 7; j++) {
if(maze[i][j] == 2)
printf("█"); else if(maze[i][j] == 1)
printf("◇"); else
printf(" ");
}
printf("\n");
}
}
return 0;
}
int visit(int i, int j) {
maze[i][j] = 1;
if(i == endI && j == endJ)
success = 1;
if(success != 1 && maze[i][j+1] == 0) visit(i, j+1);
if(success != 1 && maze[i+1][j] == 0) visit(i+1, j);
if(success != 1 && maze[i][j-1] == 0) visit(i, j-1);
if(success != 1 && maze[i-1][j] == 0) visit(i-1, j);
if(success != 1)
maze[i][j] = 0;
return success;
}
老鼠走迷宮（二）
解法
求所有路徑看起來複雜但其實更簡單，只要在老鼠走至出口時顯示經過的路徑，然後退回上一格重新選擇下一個位置繼續遞迴就可以了，比求出單一路徑還簡單，我們的程式只要作一點修改就可以了。
程式碼——C語言
#include <stdio.h>
#include <stdlib.h>
void visit(int, int);
int maze[9][9] = {{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}};
int startI = 1, startJ = 1;
// 入口
int endI = 7, endJ = 7;
// 出口
int main(void) {
int i, j;
printf("顯示迷宮：\n");
for (i = 0; i < 7; i++) {
for (j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█"); else
printf(" ");
printf("\n");
}
visit(startI, startJ);
return 0;
}
void visit(int i, int j) {
int m, n;
maze[i][j] = 1;
if(i == endI && j == endJ) {
printf("\n顯示路徑：\n");
for (m = 0; m < 9; m++) {
for (n = 0; n < 9; n++)
if(maze[m][n] == 2)
printf("█"); else if(maze[m][n] == 1)
printf("◇"); else
printf(" ");
printf("\n");
}
}
if(maze[i][j+1] == 0) visit(i, j+1);
if(maze[i+1][j] == 0) visit(i+1, j);
if(maze[i][j-1] == 0) visit(i, j-1);
if(maze[i-1][j] == 0) visit(i-1, j);
maze[i][j] = 0;
}