| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4235 人关注过本帖
标题:[求助]急求 很急 迷宫问题c程序
只看楼主 加入收藏
gaga
Rank: 1
等 级:新手上路
威 望:2
帖 子:307
专家分:0
注 册:2006-4-5
收藏
得分:0 
以下是引用tiantian403t在2006-5-27 19:19:00的发言:

谢谢你,我想要一个自己能随便输迷宫的,在求最短路径时要用多种方法的,谢谢了,很急

随便输出,你改下就可以了,
但找最短路,我还没有看到,我也不会啊,我才看到了栈了,
快考试了最近都没有时间学数据结构了


明天的明天还有明天。 可是今天却只有一个。 public Copy from 无缘今生
2006-05-27 20:44
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
以下是引用gaga在2006-5-25 13:34:00的发言:
贴子里面有,找下就能找到

2楼说的是置顶的那个经典帖子集合,里面就有迷宫问题源代码的连接,上面持异议的各位想必没去认真看过吧。建议去看下,里面有很多资源。


我的征途是星辰大海
2006-05-27 20:54
tiantian403t
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2006-5-24
收藏
得分:0 

谢谢你们

2006-05-27 22:37
miraculous
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2006-5-30
收藏
得分:0 

#include"time.h"
#include "stdio.h"
#include "graphics.h"
#include "conio.h"
#include "stdlib.h"
#define MaxX 50 /*迷宫的最大行数*/
#define MaxY 50 /*迷宫的最大列数*/
typedef struct node
{
int x;
int y;
}queue; /*定义队列,用于存放迷宫的路径*/
typedef struct
{
queue data[255];
int rear,front;
}Queue;
typedef Queue *Node;
Node result;
int X,Y; /*迷宫的大小*/
int Map[MaxX][MaxY]; /*迷宫结构*/

void init_queue() /*队列初始化*/
{
int i;
result=(Node)malloc(sizeof(Queue));
for(i=0;i<255;i++)
result->data[i].x=result->data[i].y=0;
result->front=result->rear=0;
}
void en_queue(int x,int y) /*入队*/
{
result->data[result->rear].x=x;
result->data[result->rear].y=y;
result->rear++;
}
queue del() /*删除刚入队元素*/
{
queue p;
result->rear--;
p=result->data[result->rear];
return p;
}
int empty_queue() /*判断队列是否为空*/
{
return(result->front==result->rear);
}
void Setmap() /*手工输入迷宫函数*/
{
int i,j,t;
printf("\n依次输入迷宫的结构(1为墙,0为通路):\n");
for(i=0;i<=X+1;i++)
{
for(j=0;j<=Y+1;j++)
{
if(i==0 || j==0 || i==X+1 || j==Y+1) /*在迷宫周围包上一圈1,防止搜索通路时越界*/
{
Map[i][j]=1;
continue;
}
else
{
scanf("%d",&t); /*手工输入迷宫的墙与通路*/
Map[i][j] = (t!=0) ? 1 : 0;
}
}
}
}
void AutoSetMap() /*电脑绘制迷宫*/
{
int a=20,b=10,i,j; /*a、b用于产生不同的随机数种子*/
for(i=0;i<=X+1;i++)
{
for(j=0;j<=Y+1;j++)
{
if(i==0 || j==0 || i==X+1|| j==Y+1)
{
Map[i][j]=1;
continue;
}
srand((rand()*(a++)+(b++))%65536); /*srand和rand函数配合使用,产生随机数的起始发生数据*/
Map[i][j]=rand()%2; /*产生的随机数mod2所得的余数为1或者0,作为迷宫的墙或通路*/
}
}
}
void mouse(int x,int y) /*画出当前位置*/
{
int x1,y1;
x1=105+30*(y-1);
y1=65+30*(x-1);
line(x1-10,y1,x1+10,y1); /*在通路的地方画线*/
line(x1,y1-10,x1,y1+10);
}
void erasermouse(int x,int y) /*擦除所走过的点*/
{
int x1,y1;
x1=105+30*(y-1);
y1=65+30*(x-1);
setcolor(15); /*15表示白色*/
line(x1-10,y1,x1+10,y1); /*将刚刚画过线的地方用白色再画一次,也就将刚才画的线覆盖掉*/
line(x1,y1-10,x1,y1+10);
setcolor(4); /*红色,再将当前颜色变成红色*/
}
void TIMEDELAY() /*时间延迟函数,这样动态实现时才可以看清 */
{
double i;
for(i=0;i<9e+6;i++); /*执行一个空循环,达到延时的效果*/
}
void SearchWay() /*查找最短路径*/
{
queue p;
int kill[MaxX][MaxY]={0}; /*判断是否是回路*/
int i=1,j=1,n; /*i、j用于记录所走的下标,n用来计算搜索的方向个数(8个)*/
int po; /*检查方向的计数器*/
if(Map[X][Y]&&Map[i][j])
return; /*如果入口或出口不通直接返回*/
do
{
if(!Map[i][j]&&!kill[i][j]) /*如果是通路且未访问过*/
{
en_queue(i,j); /*将要可通行的坐标入队*/
kill[i][j]=1; /*将判断标志改为1*/
mouse(i,j); /*画当前位置*/
TIMEDELAY(); /*延时*/
erasermouse(i,j); /*擦除所走过的点*/
if(!Map[i][j]) /*是通路的情况*/
{
i = i+1; /*下一个要检查的坐标 左斜上方*/
j = j+1;
}
po=0; /*计数器清零*/
}
else
{
i=result->data[result->rear-1].x; /*回溯*/
j=result->data[result->rear-1].y;
for(n=0;n<7;n++) /*在上面if语句中已经判断了一个方向,所以只要再搜索其余的7个方向即可*/
{
po++;
if(po==1)
{
j++; /*右*/
if(!Map[i][j]&&!kill[i][j])
break;
else
j--;
}
if(po==2)
{
i++; /*下*/
if(!Map[i][j]&&!kill[i][j])
break;
else
i--;
}
if(po==3)
{
i--;j++; /*右斜上*/
if(!Map[i][j]&&!kill[i][j])
break;
else
{
i++;
j--;
}
}
if(po==4)
{
i++;j--; /*左斜下*/
if(!Map[i][j]&&!kill[i][j])
break;
else
{
i--;
j++;
}
}
if(po==5)
{
i--; /*上*/
if(!Map[i][j]&&!kill[i][j])
break;
else
i++;
}
if(po==6)
{
j--; /*左*/
if(!Map[i][j]&&!kill[i][j])
break;
else
j++;
}
if(po==7)
{
i--;j--; /*左斜上*/
if(!Map[i][j]&&!kill[i][j])
break;
else
{
i++;
j++;
}
}
}
if(n==7&&kill[i][j]) /*下一步没有通路*/
{
p=del(); /*将刚入队的下标删除*/
i=p.x; /*回溯*/
j=p.y;
po=0; /*清零计数器*/
}
if(empty_queue()) /*如果队列为空,则返回*/
return;
}
}while(i!=X+1||j!=Y+1); /*还没到达迷宫边缘继续循环*/
}
void maze() /*画迷宫*/
{
int i,j;
setbkcolor(5); /*将背景颜色设置为红紫色*/
setcolor(14); /*将当前颜色设置成黄色*/
rectangle(90,50,90+Y*30,50+X*30); /*画起点是(90,50)终点是(90+Y*30,50+X*30)的框*/
for(i=80;i<50+X*30;i=i+30) /*画迷宫的行 */
line(90,i,90+Y*30,i);
for(i=120;i<90+Y*30;i=i+30) /*画迷宫的列*/
line(i,50,i,50+X*30);
for(i=1;i<=X;i++)
{
for(j=1;j<=Y;j++)
if(Map[i][j]==0)
floodfill(105+(j-1)*30,65+(i-1)*30,14); /*通路的地方变成白色*/
}
}
void print_path() /*打印迷宫路径*/
{
if(result->rear==result->front)
printf("\n\t\t此迷宫没有出路");
else
{
printf("\n入口->");
while(result->front!=result->rear)
{
printf("(%d,%d)->",result->data[result->front].x,result->data[result->front].y);
result->front++;
}
printf("出口");
}
}
int menu_select() /*菜单*/
{
int sn;
clrscr();
printf("\n\t\t迷宫问题\n");
printf("\n\t\t*********************");
printf("\n\t\t1.手动绘制迷宫");
printf("\n\t\t2.电脑绘制迷宫");
printf("\n\t\t3.退出");
printf("\n\t\t*********************");
printf("\n\t\t请选择:");
scanf("%d",&sn);
return sn;
}
main()
{
char k='y',ch;
int driver=VGA,mode=VGAHI,i;
while(k=='y')
{
switch(menu_select())
{
case 1:
clrscr();
printf("\n请输入迷宫大小X(行1<X<12)Y(列1<Y<12)!\n");
scanf("%d%d",&X,&Y);
Setmap(); /*手动创建迷宫*/
clrscr(); /*清屏*/
initgraph(&driver,&mode,""); /*切换到图形模式*/
maze(); /*画迷宫*/
SearchWay(); /*找路径*/
closegraph(); /*切换到文本模式*/
print_path(); /*打印路径*/
printf("\n\t\t请按回车返回菜单!\n");
fflush(stdin);
scanf("%c",&ch);
if(ch=='\n')
break;
case 2:
clrscr();
printf("\n请输入迷宫大小(最好不要超过12行12列)X(行1<X<12),Y(列1<Y<12)!\n");
scanf("%d%d",&X,&Y);
AutoSetMap(); /*电脑创建迷宫*/
clrscr(); /*清屏*/
initgraph(&driver,&mode,""); /*切换到图形模式*/
maze(); /*画迷宫*/
SearchWay(); /*找路径*/
closegraph(); /*切换到文本模式*/
print_path(); /*打印路径*/
printf("\n\t\t请按回车返回菜单!\n");
fflush(stdin);
scanf("%c",&ch);
if(ch=='\n')
break;
case 3:
printf("\n\t\t欢迎下次使用,再见!");
k='n';
fflush(stdin);
scanf("%c",&ch);
if(ch=='\n')
break;
}
}
}

2006-05-30 16:25
huo9527
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2006-5-13
收藏
得分:0 

我以前依照书上算法写了一个,后来让老师该了后通过了,你看看吧。
1.同学写的,真确的
#include "stdio.h"
#include "stdlib.h"
#include "process.h"
#define N 10

typedef struct lnode
{
int x;
int y;
int d;
struct lnode *next;
}lnode,*linkstack;

typedef struct
{
linkstack base;
linkstack top;
}*stack;

stack creat()
{
stack s;
s->base=(linkstack)malloc(sizeof(lnode));


if(s->base==NULL)
{
printf("Overflow");
exit(0);
}
s->base->x=50;
s->base->y=50;
s->base->d=50;
s->base->next=NULL;
s->top=s->base;
return s;
}

stack push(stack s,int r,int c,int D)
{
linkstack p;
p=(linkstack)malloc(sizeof(lnode));
p->x=r;
p->y=c;
p->d=D;
p->next=s->top;
s->top=p;

return s;
}

stack pop(stack s)
{
linkstack p;
if(s->top==s->base)
{
printf("It's empty.\nthere is no access to enter.\n");
exit(0);
}
p=s->top;
s->top=s->top->next;
free(p);
return s;
}


stack found(stack s,int a[N][N],int b[4][2])
{
int r=1,c=1,D=0,i=0,D0=0,f=0;
while(r!=8|c!=9)
{
if(a[r][c]==0)
{
if(f) /*当不能沿栈顶结点所指的方向走时,f为真*/
s->top->d=D;
D0=(D+2)%4; /*D0为准备退回时的方向*/
D=0; /*指该元素指向下一个元素的方向*/

s=push(s,r,c,D);
a[s->top->x][s->top->y]=5; /*入栈的元素,对应的数组元素做相应的改变*/
f=0;
if(D==D0)
{
D=D+1;
f=1;
}
}
else
{
f=1;
D=D+1;
if(D==D0)
{
D=D+1;
}

if(D>3)
{
a[s->top->x][s->top->y]=2; /*出栈的元素,对应数组元素做相应的改变*/
s=pop(s);
D=s->top->next->d;
D0=(D+2)%4;

}
}
for(i=0;i<4;i++)
if(i==D) /*根椐D的方向来确定下一结点的坐标*/
{
r=s->top->x+b[i][0];
c=s->top->y+b[i][1];
break;
}
}
if(s->top!=s->base)
printf("success to find!\n");
else
printf("No access to go out\n");
return s;

}

void print(int a[N][N])
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("%3d",a[i][j]);
printf("\n\n");
}
}

void main()
{
stack s;
int a[N][N]={{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,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,1,1,1,1,1,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
int b[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
s=creat();
printf("the map is:\n");
print(a);
printf("please enter to find\n");
getch();
s=found(s,a,b);
printf("the result map is:\n");
print(a);
getch();
}


2.自己写的,但也经老师改过
#define STACK_INIT_SIZE 1000
#define STACKINCREMENT 10
#define ERROR 0
#define TURE 1
//#include "alloc.h"
#include "process.h"
#include<iostream.h>
#include<conio.h>
typedef struct{
int row;
int col;
}PosType;

typedef struct{
int ord; //通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的"坐标位置"
int di; //从此通道块走向下一通道的"方向"
}SelemType;

typedef struct{
SelemType *base;
SelemType *top;
int stacksize;
}SqStack;

void InitStack(SqStack &s){ //构造栈
s.base=new SelemType[STACK_INIT_SIZE];
s.top=s.base;
// s.stacksize=STACK_INIT_SIZE;
}
void push(SqStack &s,SelemType e){ //入栈操作
//if(s.top-s.base>=s.stacksize){
//s.base=(PosType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(PosType));
//if(!s.base)exit(ERROR);
//s.top=s.base+s.stacksize;
//s.stacksize+=STACKINCREMENT;
*s.top++=e;
// cout<<"push:"<<e.seat.row<<" "<<e.seat.col<<" "<<e.di<<endl;
}

void pop(SqStack &s,SelemType &e){ //出栈操作
e=*--s.top;
// cout<<"pop: "<<e.seat.row<<" "<<e.seat.col<<" "<<e.di<<endl;
}

int StackEmpty(SqStack s){ //判断栈是否为空
if (s.top==s.base)return TURE;
return 0; }

PosType NextPos(PosType curpos,int dir){ //控制下一步走向
PosType RetPos;
switch(dir){
case 1:RetPos.row=curpos.row+1;
RetPos.col=curpos.col;break;
case 2:RetPos.row=curpos.row;
RetPos.col=curpos.col-1;break;
case 3:RetPos.row=curpos.row-1;
RetPos.col=curpos.col;break;
case 4:RetPos.row=curpos.row;
RetPos.col=curpos.col+1;break;
}return RetPos;
}

int fun(int a[10][10],PosType start,PosType end,SqStack &s){
//若迷宫中存在从入口START到出口END的通道,则求得一条存放在栈中(从栈底到栈顶),并返回TRUE,否则返回FALSE
//InitStack(s);
PosType curpos;
int curstep;
SelemType e;
curpos=start;
curstep=1;
do{
if(a[curpos.row][curpos.col]==0)
{ //当前位置可以通过,既是未走过的通道块
e.di=1;
a[curpos.row][curpos.col]=1; //通过时留下足迹
e.ord=curstep;
e.seat=curpos;
push(s,e); //加入路径
if((curpos.row==end.row)&&(curpos.col==end.col))return (TURE); //到达终点
curpos=NextPos(curpos,1); //下一步是当前位置的东邻
curstep++; //探索下一步
}
else{
if(!StackEmpty(s)){
pop(s,e);
while((e.di==4)&&(!StackEmpty(s))){
a[e.seat.row][e.seat.col]=1;
pop(s,e); //留下不能通过的足迹,并退一步

}
if(e.di<4){
e.di++;
push(s,e);
curpos=NextPos(e.seat,e.di);
}
}

}
}while(!StackEmpty(s));
return (ERROR);
}

int main(){
SqStack s;InitStack(s);
int a[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,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,1,1}
};
int i,j;
PosType start,end;
start.row=1;
start.col=1;
end.row=8;
end.col=8;
SelemType f;
//for(i=0;i<10;i++)
// a[i][0]=a[i][9]=a[0][i]=a[9][i]=1;
//a[1][3]=a[1][7]=a[2][3]=a[2][7]=a[3][5]=a[3][6]=1;
//a[4][2]=a[4][3]=a[4][4]=a[5][4]=a[6][2]=a[6][6]=1;
//a[7][2]=a[7][3]=a[7][4]=a[7][6]=a[7][7]=1;
// for(i=0;i<10;i++)
// {for(j=0;j<10;j++)
// if(a[i][j]!=1) a[i][j]=0;}
//a[8][8]=8;
for(i=0;i<10;i++)
{{for(j=0;j<10;j++)cout<<a[i][j];}
cout<<"\n";}
fun(a,start,end,s);

while(!StackEmpty(s))
{
pop(s,f);
cout<<f.seat.row<<"\t"<<f.seat.col<<endl;
}
cout<<"\n";
return 0;
}

2006-05-31 22:50
ljj1903
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-6-8
收藏
得分:0 
??
2006-06-08 23:34
快速回复:[求助]急求 很急 迷宫问题c程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018125 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved