awe的程設筆記

相信有學過遞迴的人，多少應該對於利用遞迴進行迷宮演算、八皇后、騎士行等等多少有一些瞭解。

今天要來介紹的是在資料結構當中如何利用堆疊讓程式自動解迷宮的方式，且效率比起遞迴來說要好上很多。

這樣的演算技巧也比較接近人類解決迷宮的思路過程，怎麼說呢？

且讓我們以這樣的 8x8 迷宮為例，相信聰明的你應該已經知道解題的路徑了，但先別急，電腦可沒那麼聰明。

一起來教教電腦怎麼解吧！

# # # # # # # #
. . . # . . . .
# # . # . # . #
# . . # # # . #
# # . # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #

首先，我們建立一個記號矩陣，以便我們未來記錄哪些路徑是我們走過的，如果走過的路徑最後帶領我們進入死路，

將來也可以因為記號矩陣的關係，告訴我們這條路並不可行，以便嘗試另一條可能的路。

以下是我們初始的記號矩陣：

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

接下來，我們請電腦當到達一個位置時，先依序判斷 右方、左方、下方、上方 是否可以行進，

(所謂可行進，是以該位置的迷宮字元不是'#'，且記號矩陣元素是 0 來判斷)

而且到達一個可行進的位置後，我們需要把該位置的座標放進堆疊，並且將該位置記號矩陣元素加1(用來表示走過)

另外，堆疊的頂端元素 (TOP)就是我們現在行進到的位置

依據這個準則先運行三步(因為前三步的右方均可行)：

堆疊元素>(1,0),(1,1),(1,2)

記號矩陣>

0 0 0 0 0 0 0 0 0 

1 1 1 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

...........................

此時，問題來了，因為 (2,1) 這個位置的右方不可行，我們依照準則嘗試左方，但也不可行(因為記號元素不是 0)，再來發現下方可以走

依照這個情形持續兩步：

此時堆疊元素>(1,0),(1,1),(1,2),(2,2),(3,2)

記號矩陣>

0 0 0 0 0 0 0 0 0 

1 1 1 0 0 0 0 0 0 

0 0 1 0 0 0 0 0 0 

0 0 1 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

.........................

在這一步中，我們先發現右方不可行，但左方卻可行於是我們往左變成這樣

堆疊元素>(1,0),(1,1),(1,2),(2,2),(3,2),(2,2)

記號矩陣>

0 0 0 0 0 0 0 0 0 

1 1 1 0 0 0 0 0 0 

0 0 1 0 0 0 0 0 0 

0 1 1 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

.........................

但是，這卻是一條死路，那該怎麼辦呢？沒關係，我們把堆疊 pop out(彈出)，變成

堆疊元素>(1,0),(1,1),(1,2),(2,2),(3,2)

記號矩陣>

0 0 0 0 0 0 0 0 0 

1 1 1 0 0 0 0 0 0 

0 0 1 0 0 0 0 0 0 

0 1 1 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

.........................

這下情況便成了，我們現在的位置在(3,2)，簡言之就是走回頭路啦！，但是這樣造成了什麼結果？

好，我們平心靜氣，在 (3,2) 這位置我們發現，右方依然不可行(因為右邊的迷宮元素是'#')，那我們嚐試左方，

LADYS & GENTELMAN 神奇的來了，和剛才進入 (3,2)不同的是，"左邊也不可行了(因為記號矩陣為 1)"，

那就嘗試另一個方向，也就是下方了。

繼續依此類推，縱使我們先前走過了一些冤枉路，但是最後抵達終點(堆疊頂端元素為 (1,7) )時可以發現，

"堆疊內所有的元素就是我們迷宮的解"

如此一來，我們就可以實現不用遞迴也可以解迷宮的方式了，酷吧！

那麼廢話不多說，來把它用C++寫出來吧！！

Stack.h (堆疊定義)

#ifndef STACK_H
#define STACK_H

#include<iostream>
#include<cstring>
using namespace std;

template <class T>
class Stack
{
public:
Stack(const int StackCapacity = 10):capacity(StackCapacity)
{
itemArray = new T[capacity];
memset(itemArray,0,capacity*sizeof(T));
top = -1;
}
~Stack()
{
delete[]itemArray;
}
bool IsEmpty()const
{
return top == -1;
}

T& Top()
{
if(IsEmpty()) throw "Stack is empty\n";
return itemArray[top];
}

void Push(const T &addItem)
{
if(top == capacity -1)
{
//resize the array
T* tempArray = new T[2*capacity];
memset(tempArray,0,2*capacity*sizeof(T));
memcpy(tempArray,itemArray,capacity*sizeof(T));
delete[] itemArray;
itemArray = tempArray;
capacity *=2;
}
itemArray[++top] = addItem;
}

void Pop()
{
itemArray[top--].~T();
}

void Print()const
{
for(int i = 0 ; i <= top ; i++)
{
cout<<itemArray[i]<<"\t";
}
cout<<endl;
}
int getSize(){return top+1;}

private:
int top;
int capacity;
T* itemArray;
};
#endif

Position.h (位置元素的定義)

#ifndef POSITION_H
#define POSITION_H

#include<iostream>

using namespace std;
class Position
{
public:
Position(){}
Position(int x,int y)
{
xPos = x;
yPos = y;
}
int xPos;
int yPos;
};

ostream& operator << (ostream& os,const Position pos)
{
os << "("<<pos.xPos<<" ,"<<pos.yPos<<")";
return os;
}
#endif

main.cpp (主程式)

#include"Stack.h"
#include"Position.h"
#include<iostream>
#include<cstring>
char maze[8][8] = {
{ '#','#', '#' ,'#' ,'#', '#', '#' ,'#' },
{ '.','.', '.' ,'#' ,'.', '.', '.' ,'.' },
{ '#','#', '.' ,'#' ,'.', '#', '.' ,'#' },
{ '#','.', '.' ,'#' ,'#', '#', '.' ,'#' },
{ '#','#', '.' ,'#' ,'.', '#', '.' ,'#' },
{ '#','.', '.' ,'.' ,'.', '#', '.' ,'#' },
{ '#','#', '.' ,'.' ,'.', '.', '.' ,'#' },
{ '#','#', '#' ,'#' ,'#', '#', '#' ,'#' },
};

int path[8][8] = {};

typedef struct _dim
{
int xPos;
int yPos;
}dim;
dim Dim[4] = {
{0,1},
{0,-1},
{-1,0},
{1,0}
};

using namespace std;

int main()
{
Stack<Position> stack1(10);
Position start(1,0);
stack1.Push(start);
path[1][0] ++;
int dimention = 0;

while(dimention <= 4 && !stack1.IsEmpty())
{
Position nowPos(stack1.Top().xPos,stack1.Top().yPos);
if(dimention == 4) {dimention = 0;stack1.Pop();continue;}
if(nowPos.xPos == 1 && nowPos.yPos == 7) break;
Position nextPos(nowPos.xPos + Dim[dimention].xPos,nowPos.yPos + Dim[dimention].yPos);
if(maze[nextPos.xPos][nextPos.yPos] != '#' && path[nextPos.xPos][nextPos.yPos] == 0)
{
stack1.Push(nextPos);
path[nextPos.xPos][nextPos.yPos] ++;
dimention = 0;
}
else dimention++;
}
if(stack1.IsEmpty()) {cout<<"there's no way out"<<endl; return 0;}
cout<<"\n\nthe shortest path is:"<<endl<<"-----------------------"<<endl;
stack1.Print();
cout<<"total step is: "<<stack1.getSize()<<endl;
while(!stack1.IsEmpty())
{
int x = stack1.Top().xPos;
int y = stack1.Top().yPos;
maze[x][y] ='x';
stack1.Pop();
}
cout<<"\nShow the path:"<<endl<<"---------------------------"<<endl;
for(int i = 0 ; i<8 ;i++)
{
for(int j = 0 ; j < 8 ; j++)
cout<<maze[i][j]<<' ';
cout<<endl;
}
return 0;

}

最後的執行結果：

the shortest path is:
-----------------------
(1 ,0) (1 ,1) (1 ,2) (2 ,2) (3 ,2) (4 ,2) (5 ,2) (5 ,3) (5 ,4) (6 ,4) (6 ,5) (6 ,6) (5 ,6) (4 ,6) (3 ,6) (2 ,6) (1 ,6) (1 ,7)
total step is: 18

Show the path:
---------------------------

# # # # # # # #
x x x # . . x x
# # x # . # x #
# . x # # # x #
# # x # . # x #
# . x x x # x #
# # . . x x x #
# # # # # # # #