#include <iostream>
using namespace std;
#define GRID_NUM 11 //迷宫格子数
//利用矩阵来存储迷宫地图
//0表示墙，1表示路
//探索到的死路将被赋为-1
int map[GRID_NUM][GRID_NUM]=
{
{0,0,0,0,0,0,0,0,0,0,0},
{99,1,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,0,0,0},
{0,0,1,0,0,0,0,1,0,0,0},
{0,1,1,1,1,0,0,1,0,0,0},
{0,1,0,0,0,0,0,1,0,0,0},
{0,1,1,1,1,1,1,1,1,1,0},
{0,0,0,0,1,0,0,1,0,0,0},
{0,0,0,0,1,0,0,1,0,0,0},
{0,0,0,0,0,0,0,1,1,1,100},
{0,0,0,0,0,0,0,0,0,0,0}
};
//==================================================================
//从当前位置探索可通路径（死路除外）的条数，并返回
int switchmany(int *current){
int s=0;
if(*(current-GRID_NUM)>=1){s++;}
if(*(current+GRID_NUM)>=1){s++;}
if(*(current+1)>=1){s++;}
if(*(current-1)>=1){s++;}
return s;
}
//寻路，探索某个确定的方向上的路是否可通
int whichway(int*current){
if(*(current-GRID_NUM)>=1){return 1;}//
if(*(current+GRID_NUM)>=1){return 2;}
if(*(current+1)>=1){return 3;}
if(*(current-1)>=1){return 4;}
return -1;
}
int whichway2(int*current){
if(*(current-GRID_NUM)==-1){return 1;}
if(*(current+GRID_NUM)==-1){return 2;}
if(*(current+1)==-1){return 3;}
if(*(current-1)==-1){return 4;}
return -1;
}
//根据给定的whichway向某一确定的方向走一步
int* go(int *current,int whichway){
switch (whichway){
case 1:current=current-GRID_NUM;break;
case 2:current=current+GRID_NUM;break;
case 3:current++;break;
case 4:current--;break;
}
return current;
}
//===============================输出==================================
//输出路径
void output(int *inc[100],int *a,int all){
cout<<"探索迷宫路径"<<endl;
int **pc;
pc=inc;
int x,y,i;
cout<<"(1,2) --> ";
for (int k=0;k<all;k++){
i=*pc-a+1;
x=i%GRID_NUM;
if(x==0){
y=(i-x)/GRID_NUM;
x=GRID_NUM;
}else{
y=(i-x)/GRID_NUM+1;
}
cout<<"("<<x<<","<<y<<") --> ";
pc++;
}
cout<<"("<<x+1<<","<<y<<")"<<endl;
}
//==================================main===================================
int main()
{
int *b[80],*allpath[100];//保存足迹
int **top=b,**pc=allpath;
int *curPos=&map[1][0];//将迷宫的入口位置赋给curPos
*top=curPos;//当前位置进栈
*curPos=-1;
curPos++;//先向右走一步
top++;
*curPos=-1;
*top=curPos;//当前位置进栈
int all=0;//all保存总足印数
//------------------------------------------
while(*curPos!=100){//没走到迷宫出口
if(switchmany(curPos)==0){
*curPos=0;
while(curPos!=(*top)){
*pc=curPos;
pc++;
all++;
*curPos=0;
curPos=go(curPos,whichway2(curPos));
}
curPos=*top;
top--;
}
if(switchmany(curPos)==1){
while(switchmany(curPos)==1){
*curPos=-1;
*pc=curPos;
pc++;
all++;
curPos=go(curPos,whichway(curPos));
}
}
if(switchmany(curPos)>1){
*curPos=-1;
top++;
*top=curPos;//当前位置进栈
*pc=curPos;
pc++;
all++;
curPos=go(curPos,whichway(curPos));
}
}
output(allpath,&map[0][0],all);
return 0;
}posted on 2008-12-02 09:22
Gaojingluo 阅读(104)
评论(0) 编辑 收藏 引用