迷宫数据
8 8 //迷宫的大小，行数与列数
1 1 8 8 //1 1 表入口位置 8 8 表出口位置
0 0 1 0 0 0 1 0 //以下表迷宫，1表示墙、0表示通路，为避免走的过程中越界，最好在四周加上以堵墙。
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 1 0 0 0 0 0 0
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 50
#define ERROR -1
#define OK 0
#define FALSE 0
#define TRUE 1
typedef enum{RIGHT,DOWN,LEFT,UP} Direction
typedef enum{YES,NO} MarkTag
typedef struct position{//迷宫中位置的坐标
int x
int y
}Position
typedef struct{ //当前位置在路径中的序号
int order //当前位置在迷宫中的坐标
Position seat //从当前位置走到下一位置的方向
Direction di //栈元素的类型
}SElemType
typedef struct{
SElemType *elem
int top
}Stack
char maze[MAXSIZE+2][MAXSIZE+2] //用二维数组表示迷宫
int InitStack(Stack *S){ //创建一个空栈
S->elem=(SElemType *)malloc(MAXSIZE*MAXSIZE*sizeof(SElemType))
if(!S->elem)
return ERROR
S->top=0
return OK
}
int Push(Stack *S,SElemType e){//元素e入栈
if(S->top>=MAXSIZE*MAXSIZE)
return ERROR
S->elem[S->top++]=e
return OK
}
int Pop(Stack *S,SElemType e){//栈顶元素出栈，由e带回栈顶元素
if(S->top<=0)
return ERROR
*e=S->elem[--S->top]
return OK
}
int Empty(Stack S){ //若栈为空，返回TRUE,否则返回FALSE
if(S.top==0)
return TRUE
return FALSE
}
int createMaze(char *filename,Position *startpos,Position *endpos){ //从文件filename读入数据创建迷宫，由参数带回入口位置和出口位置
FILE *fp
int i,j,rows,cols,temp
Position start,end
fp=fopen(filename,"r")
if(!fp){
printf("open file %s error!\n",filename)
return ERROR
}
if(!feof(fp)){
fscanf(fp,"%d %d",&rows,&cols) //读入迷宫的行数和列数
fscanf(fp,"%d %d",&start.x,&start.y) //读入迷宫的入口位置
fscanf(fp,"%d %d",&end.x,&end.y) //读入迷宫的出口位置
}
for(i=1i<=rowsi++) //读入迷宫数据
for(j=1j<=colsj++){
fscanf(fp,"%d",&temp)
maze[i][j]=48+temp
}
fclose(fp)
//在迷宫四周加墙
for(i=0,j=0i<=rows+1i++) maze[i][j]='1'
for(i=0,j=cols+1i<=rows+1i++) maze[i][j]='1'
for(i=0,j=0j<=cols+1j++) maze[i][j]='1'
for(i=rows+1,j=0j<=cols+1j++) maze[i][j]='1'
*startpos=start
*endpos=end
return OK
}
int canPass(Position curpos){
if(maze[curpos.x][curpos.y]=='0')
return TRUE
return FALSE
}
void markPos(Position curpos,MarkTag tag){ //为已走过的位置标记
switch(tag){
case YES: maze[curpos.x][curpos.y]='.' break //路径标记
case NO: maze[curpos.x][curpos.y]='#' break //死胡同标记
}
}
Position nextPos(Position curpos,Direction dir){ //根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标
Position nextpos
switch(dir){
case RIGHT: nextpos.x=curpos.xnextpos.y=curpos.y+1break
case DOWN: nextpos.x=curpos.x+1nextpos.y=curpos.ybreak
case LEFT: nextpos.x=curpos.xnextpos.y=curpos.y-1break
case UP:nextpos.x=curpos.x-1nextpos.y=curpos.ybreak
}
return nextpos
}
Direction nextDir(Direction dir){
switch(dir){ //按照RIGHT DOWN LEFT UP的次序进行路径探索
case RIGHT: return DOWN
case DOWN: return LEFT
case LEFT: return UP
}
}
/*若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈S中，并返回TRUE，若不存在则返回FALSE*/
int Solve(Stack *S,Position start,Position end){
Position curpos
SElemType e
int curstep=1
if(InitStack(S)==ERROR)
return FALSE
curpos=start
do{
if(canPass(curpos)){ //当前位置可以通过
markPos(curpos,YES)//留下足迹
e.order=curstep
e.seat=curpos
e.di=RIGHT
Push(S,e)
if(curpos.x==end.x &&curpos.y=end.y)
return TRUE//找到从入口到出口的通道
curpos=nextPos(curpos,RIGHT)
curstep++
}
else{
if(!Empty(*S)){ //当前位置不能通过
if(Pos(S,&e)==ERROR)
return FALSE
while(e.di==UP &&!Empty(*S)){ //4个方向都找不到通路，则回溯
curpos=e.seat
markPos(curpos,NO)
if(Pop(S,&e)==ERROR)
return FALSE
}
if(e.di!=UP){ //4个方向还没有探索完
e.di=nextDir(e.di)
Push(S,e) //换下一个方向探索
curpos=nextPos(e.seat,e.di)
}
}
}while(!Empty(*S))
return FALSE
}
void main(void){
Position startPos,endPos
Stack path
SElemType e
char *fname="in.txt"
if(createMaze(fname,&startPos,&endPos)==ERROR) return
Solve(&path,startPos,endPos)
while(!Empty(path)){ //输出出口到入口的路径
Pop(&path,&e)
printf("(%d,%d)\n",e.seat.x,e.seat.y)
}
}
1、可以用“*”来代表老鼠，“|”来代表墙，空格来代表路。每走一步用system("cls")刷新一次屏幕。2、墙不可穿过代表，墙与周围的格子没有边。
3、规定一个时间t，若在t步之内没有走到粮仓，则输出无解。
4、这个简单，无非就是修改条件，从而修改整个图。
5、所用路径可以用深搜（回朔）来解决，最短路就用广搜来解决。最短路也可以用Dijstra算法、floyd算法等，但广搜是最简单的。
具体的程序你自己实现吧，如果写不出来，就去请教一下你们学校的ACMer，他们应该会比较熟悉。加油吧。
