[原创]迷 宫 问 题

#include<iostream>
#include<time.h>

using namespace std;

const int MaxX = 50; //最大列数
const int MaxY = 50; //最大行数

struct Point //点
{
int x;
int y;
};

class CLabyrinth
{
int X,Y; //迷宫的大小
int Map[MaxX][MaxY]; //迷宫结构
Point Result[255]; //存放正确的路径(栈)
int top; //栈顶（指针）
public:
CLabyrinth(); //得到迷宫尺寸
void SetMap(); //手工设置迷宫结构
void AutoSetMap(); //自动设置迷宫结构
void ShowMap(); //显示迷宫
void SearchWay(); //搜索通路
void ShowResult(); //显示通路
};

CLabyrinth::CLabyrinth()
{
cout<<"\t\t迷宫问题\t\t\n"
<<"输入迷宫的大小X*Y(最大为50*50):\n"
<<"不建议超过8列，因为绘出的地图将不会显示\n";
int x,y;
cin>>x>>y;
X = (x>48) ? 50 : x+2; //多两个单位是存放迷宫外壁
Y = (y>48) ? 50 : y+2;
top=-1;
}

void CLabyrinth::SetMap()
{
cout<<"\n依次输入迷宫的结构(1为有障碍，0为无障碍):\n"
<<"前进方向有8个,分别是上、下、左、右、左上、左下、右上、右下\n";
for(int i=0,j,t;i<X;i++)
for(j=0;j<Y;j++)
{
if(i==0 || j==0 || i==X-1 || j==Y-1) //在迷宫周围包上一圈1，防止搜索通路时越界
{
Map[i][j]=1;
continue;
}
cin>>t;
Map[i][j] = (t!=0) ? 1 : 0;
}
}

void CLabyrinth::AutoSetMap()
{
cout<<"\n前进方向有8个,分别是上、下、左、右、左上、左下、右上、右下\n";
int a(39),b(72);
for(int i=0,j;i<X;i++)
{
srand((unsigned)time(NULL));
for(j=0;j<Y;j++)
{
if(i==0 || j==0 || i==X-1 || j==Y-1)
{
Map[i][j]=1;
continue;
}
srand((rand()*(a++)+(b++))%65536);
Map[i][j]=rand()%2;
}
}
}

void CLabyrinth::ShowMap()
{
if(Y>10) return;
cout<<"\n迷宫示意图为:\n";
for(int i=1,j;i<X-1;i++)
{
for(j=1;j<Y-1;j++)
{
if(i==1&&j==1) cout<<"\n\t入口->";
else cout<<"\t ";
cout<<Map[i][j];
}
if(i==X-2&&j==Y-1) cout<<"->出口";
cout<<endl;
}
}

void CLabyrinth::SearchWay()
{
if(Map[X-2][Y-2]) return; //如果出口不通直接返回
int i(X-2),j(Y-2); //出口的坐标 从出口向入口找路
int pow; //检查方向的计数器
do
{

if(!Map[i][j])
{
Result[++top].x = i; //将要可通行的坐标入栈
Result[top].y = j;
if(Result[top].x==1&&Result[top].y==1) break; //如果找到了入口退出循环
i = i-1; //下一个要检查的坐标 左斜上方
j = j-1;
pow=0; //计数器清零
}
else
{
pow++;
i = Result[top].x; //取出栈顶元素 上一次的可通行坐标
j = Result[top].y;
switch(pow)
{
case 1: i--; break; //上
case 2: j--; break; //左
case 3: i--;j++; //右斜上
if(i==Result[top-1].x && j==Result[top-1].y) //若是来路
pow++;
else break;
case 4: i++;j--; //左斜下
if(i==Result[top-1].x && j==Result[top-1].y)
pow++;
else break;
default: Map[i][j] = 1;i = Result[--top].x;j = Result[top].y; //将该坐标设为不可通行 再回到上一次可通行坐标
}
}
}while(top!=-1); //栈不为空继续循环
}

void CLabyrinth::ShowResult()
{
if(top==-1)
{
cout<<"\n此迷宫没有通路!!!\n";
return;
}
cout<<"\n此迷宫的其中一条通路为:\n入口";
for(;top!=-1;top--)
cout<<"->("<<Result[top].x<<','<<Result[top].y<<')';
cout<<"->出口\n";
}

void main()
{
CLabyrinth lab;
while(1)
{
cout<<"\n1、手工绘制迷宫\n"
<<"2、电脑绘制迷宫(很大几率绘制不出有通路地图)\n";
int usr;
cin>>usr;
if(usr==1) lab.SetMap();
else lab.AutoSetMap();
lab.ShowMap();
lab.SearchWay();
lab.ShowResult();
cout<<"再来一次(Y/N)?";
char again;
cin>>again;
if(again!='Y'&&again!='y') break;
}
}

可能因为找路的算法问题，有些时候会小绕一点点或在一个点停留一下下~~

[此贴子已经被作者于2006-1-8 4:39:55编辑过]