C语言 老鼠走迷宫

Question

求
C语言 老鼠走迷宫
题目和图

Answer 1

可以给你点提示：迷宫 可用个二维数组表示。求解方法是：从入口出发，顺某个方向走，若能过去，继续；否则，沿着原路返回，换方向继续走，直到所有可能的通路都被找到为止。为保证在任何位置上都能沿原路退回，需要一个先进后出的栈结构保存从入口到当前位置的路径。这里，给个算法的思想，不实现图形界面了。假设迷宫数据存放在一txt中：

迷宫数据

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=1;i<=rows;i++) //读入迷宫数据
for(j=1;j<=cols;j++){
fscanf(fp,"%d",&temp);
maze[i][j]=48+temp;
}
fclose(fp);
//在迷宫四周加墙
for(i=0,j=0;i<=rows+1;i++) maze[i][j]='1';
for(i=0,j=cols+1;i<=rows+1;i++) maze[i][j]='1';
for(i=0,j=0;j<=cols+1;j++) maze[i][j]='1';
for(i=rows+1,j=0;j<=cols+1;j++) 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.x; nextpos.y=curpos.y+1; break;
case DOWN: nextpos.x=curpos.x+1; nextpos.y=curpos.y; break;
case LEFT: nextpos.x=curpos.x; nextpos.y=curpos.y-1; break;
case UP: nextpos.x=curpos.x-1; nextpos.y=curpos.y; break;
}
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);
}
}

Answer 2

每走过一个点，要把走过的点的坐标由0改成其他值，如2，这样就不会在朝回走，造成循环了，嘿嘿，我写的如下：
#include<stdio.h>
#include<stdlib.h>
#define
M
15
#define
N
15
struct
mark
//定义迷宫内点的坐标类型
{
int
x;
int
y;
};
struct
Element
//"恋"栈元素，嘿嘿。。
{
int
x,y;
//x行,y列
int
d;
//d下一步的方向
};
typedef
struct
LStack
//链栈
{
Element
elem;
struct
LStack
*next;
}*PLStack;
/*************栈函数****************/
int
InitStack(PLStack
&S)//构造空栈
{
S=NULL;
return
1;
}
int
StackEmpty(PLStack
S)//判断栈是否为空
{
if(S==NULL)
return
1;
else
return
0;
}
int
Push(PLStack
&S,
Element
e)//压入新数据元素
{
PLStack
p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return
1;
}
int
Pop(PLStack
&S,Element
&e)
//栈顶元素出栈
{
PLStack
p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return
1;
}
else
return
0;
}
/***************求迷宫路径函数***********************/
void
MazePath(struct
mark
start,struct
mark
end,int
maze[M][N],int
diradd[4][2])
{
int
i,j,d;int
a,b;
Element
elem,e;
PLStack
S1,
S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2;
//入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1;
//开始为-1
Push(S1,elem);
while(!StackEmpty(S1))
//栈不为空
有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1;
//下一个方向
while(d<4)
//试探东南西北各个方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x
&&
b==end.y
&&
maze[a][b]==0)
//如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886;
//方向输出为-1
判断是否到了出口
Push(S1,elem);
printf("\n0=东
1=南
2=西
3=北
886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
while(S1)
//逆置序列
并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return;
//跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(∩_∩)o...
}
if(maze[a][b]==0)
//找到可以前进的非出口的点
{
maze[a][b]=2;
//标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
//当前位置入栈
i=a;
//下一点转化为当前点
j=b;
d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径\n");
}
/*************建立迷宫*******************/
void
initmaze(int
maze[M][N])
{
int
i,j;
int
m,n;
//迷宫行,列
printf("请输入迷宫的行数
m=");
scanf("%d",&m);
printf("请输入迷宫的列数
n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为o(∩_∩)o...\n");
for(i=0;i<=m+1;i++)
//加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++)
//输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d
",maze[i][j]);
printf("\n");
}
}
void
main()
{
int
sto[M][N];
struct
mark
start,end;
//start,end入口和出口的坐标
int
add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量
方向依次为东西南北
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add);
//find
path
system("PAUSE");
}