#include <iostream>
#include <fstream>
#include<stack>
using namespace std;
struct Pos
{
int x;
int y;
int di;
};
void mazePath();
void printMazePath();
#define MAZE_SIZE = 10
定義一個迷宮,0表示通道,1表示牆
int maze[10][10] =
{
{0,1,1,1,1,1,1,1,1,1},
{0,0,0,1,1,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,0,0}
};
stack <Pos> posStack;
int xe = 9;
int ye = 9;
ofstream ff("me.txt");
int main(void)
{
Pos pos;
pos.x = 0;
pos.y = 0;
pos.di = 0;
posStack.push(pos);
mazePath();
system("PAUSE");
return 0;
}
void mazePath()
{
if(posStack.empty())
{
//ff<<"No answer"<<endl;
return;
}
Pos pos = posStack.top();
if(pos.x==xe && pos.y==ye)
{
//ff<<"Over"<<endl;
printMazePath();
//以下代碼開啟,表示求出所有可能路徑
posStack.pop();
maze[pos.y][pos.x] = 0;
mazePath();
return;
}
if(pos.di<4)
{
int nextX;
int nextY;
switch(pos.di)
{
case 0:
nextX = pos.x+1;
nextY = pos.y;
break;
case 1:
nextX = pos.x;
nextY = pos.y+1;
break;
case 2:
nextX = pos.x-1;
nextY = pos.y;
break;
case 3:
nextX = pos.x;
nextY = pos.y-1;
break;
default:
break;
}
if((nextX>=0 && nextX<10) && (nextY>=0 && nextY<10) && (maze[nextY][nextX]==0))
{
pos.di += 1;
posStack.pop();
posStack.push(pos);
Pos nextPos;
nextPos.di = 0;
nextPos.x = nextX;
nextPos.y = nextY;
posStack.push(nextPos);
maze[pos.y][pos.x] = -1;
//ff<<"NextOK"<<" "<<pos.x<<" "<<pos.y<<" "<<pos.di-1<<endl;
mazePath();
}
else
{
pos.di += 1;
posStack.pop();
posStack.push(pos);
//ff<<"NextNotOK"<<" "<<pos.x<<" "<<pos.y<<" "<<pos.di<<endl;
mazePath();
}
}
else
{
//該位置不同,從棧頂删除,且mg[][]=0
//ff<<"Back"<<" "<<pos.x<<" "<<pos.y<<" "<<pos.di<<endl;
posStack.pop();
maze[pos.y][pos.x] = 0;
mazePath();
}
}
void printMazePath()
{
stack <Pos> backupStack;
ff<<"Path:";
while(!posStack.empty())
{
Pos pos = posStack.top();
posStack.pop();
backupStack.push(pos);
}
while(!backupStack.empty())
{
Pos pos = backupStack.top();
backupStack.pop();
posStack.push(pos);
ff<<"<"<<pos.x<<","<<pos.y<<"> ";
}
ff<<endl;
}