全部栏目

首页 热点资讯 中小学知识 大学知识 出国留学 考研考公

跪求:迷宫求解的程序代码?

发布网友 发布时间：2024-10-21 10:19

我来回答

共3个回答

热心网友 时间：2024-10-21 15:04

请把C++的注释风格改成风格的,两个程序都调试通过!

////////////////////////////////////////////////////////////////////////////////
程序1
#include<stdio.h>
#define N1 11
#define N2 10

int getpath(int maze[N1][N2])//在迷宫中探路的函数
{
int stack[N1*N2][2];
int i,x=1,y=1,ok,top=0;//可通路径上第一个点（入口点）的坐标进入路径数组stack
stack[top][0]=x;
stack[top][1]=y;//循环探路。加1则向前，减1则退回一步

while (1)
{
ok=0;//标志能否向前
if (maze[x][y+1]==0)
{y=y+1;ok=1;}//向右
else
if (maze[x+1][y]==0)
{x=x+1;ok=1;}//向下
else
if (maze[x][y-1]==0)
{y=y-1;ok=1;}//向左
else
if (maze[x-1][y]==0)
{x=x-1;ok=1;}//向上

if (!ok)//4方向均不通
{
top--;
if (top==0)//栈空，无出路
{
printf("迷宫无出路\n");
return 0;
}
x=stack[top][0];//回退后路径上最后一个点的X坐标存入X
y=stack[top][1];//回退后路径上最后一个点的Y坐标存入Y
}
else//若能走通，
{
maze[x][y]=2;//将已经走过的点标记为2
top++;
stack[top][0]=x;//新进入的点的X坐标进入路径数组
stack[top][1]=y;//新进入的点的Y坐标进入路径数组

if (x==N1-2&&y==N2-2)//到达出口
{
printf("路径为：\n");
for(i=0;i<top;i++)
{
printf("(%d,%d)-->",stack[i][0],stack[i][1]);
if((i+1)%5==0)
printf("\n");
}
printf("(%d,%d)\n",stack[top][0],stack[top][1]);
return 1;
}
}
}
}

void printmaze(maze)//输出迷宫数组函数
int maze[N1][N2];
{
int i,j;
printf("迷宫数组为：\n");
for (i=0;i<N1;i++)
{
for (j=0;j<N2;j++)
printf("%2d",maze[i][j]);
printf("\n");
}
}

main()
{
int A[N1][N2]=
{
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,1,1,
1,0,1,1,1,0,0,1,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,1,1,
1,0,1,1,1,1,0,0,1,1,
1,1,1,0,0,0,1,0,1,1,
1,1,1,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1};

printmaze(A);
getpath(A);
}
//////////////////////////////////////////////////////////////////////
程序2
#include<stdio.h>
#include<stdlib.h>

#define OVERFLOW -1
#define MAX 100
#define N 11

typedef struct
{
int x;
int y;
int d;
}Data;

typedef struct
{
int pos;
Data data[MAX];
}SNode,*Stack;

Stack InitStack()
{
Stack pStack;
pStack=(Stack)malloc(sizeof(SNode));
if(!pStack)
exit(OVERFLOW);
pStack->pos=-1;
return pStack;
}

int IsEmpty(Stack stack)
{
return stack->pos==-1;
}

void Push(Stack pStack,Data x)
{
if(pStack->pos>=MAX-1)
exit(OVERFLOW);
else
{
pStack->pos++;
pStack->data[pStack->pos]=x;
}
}

void Pop(Stack pStack)
{
if(pStack->pos==-1)
exit(OVERFLOW);
else
pStack->pos--;
}

Data GetTop(Stack pStack)
{
return pStack->data[pStack->pos];
}

Data SetStackElem(int x,int y,int d)
{
Data element;
element.x=x;
element.y=y;
element.d=d;
return element;
}

void DisplayPath(Stack pStack)
{
Data element;
printf("The path is:\n");
while(!IsEmpty(pStack)) //多了个;
{
element=GetTop(pStack);
Pop(pStack);
printf("The node is: %d %d\n",element.x,element.y);
}
}

void MazePath(int maze[][N],int direction[][2],int x1,int y1,int x2,int y2)
{
int i,j,k,g,h;
Stack pStack;
Data element;
pStack=InitStack();
maze[x1][y1]=2;
Push(pStack,SetStackElem(x1,y1,0));

while(!IsEmpty(pStack))//以前多了一个;
{
element=GetTop(pStack);
Pop(pStack);
i=element.x;
j=element.y;
k = element.d;

while (k<=3)//用while
{
g=i+direction[k][0];
h=j+direction[k][1];
if(g==x2&&h==y2&&maze[g][h]==0)
{
Push(pStack,SetStackElem(i,j,k));//把路径上最后一个点放入
DisplayPath(pStack);
return;//怎么会有返回值?
}

if(maze[g][h]==0)
{
maze[g][h]=2;
Push(pStack,SetStackElem(i,j,k+1));
i=g;
j=h;
k=0;
}
else
k++;
}
}
printf("The path has not been found\n");
}

void main()
{
int direction[][2]={0,1,1,0,0,-1,-1,0};
int maze[][N]=
{
1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1
};
MazePath(maze,direction,1,1,6,9);
}

热心网友 时间：2024-10-21 15:03

#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <graphics.h>
#define N 22
#define M 22
#define MAXLEN 200;
int bg[M][N];
struct square{
int x;
int y;
int direc;
}p[200];
void makebg(int,int);
void drawbg(int[][],int,int,int,int,int);
void drawman(int,int,int);
void rect(int,int,int,int);

void main(){/* main()开始 */
int step=20;
int len=10;
int size=20;
int x=0,y=0,x0=0,y0=0;
int i=0,j=0,k=0,count=0;
int gdriver=DETECT,gmode;
char ch;
int direc;
makebg(M,N);
/* registerbgidriver(EGAVGA_driver);
initgraph(&gdriver,&gmode,"c:\\turboc2");*/
initgraph(&gdriver,&gmode,"c:\\tc20\\bgi");
cleardevice();
setwritemode(XOR_PUT);
settextstyle(1,0,3);
setcolor(GREEN);
outtextxy(100,180,"Press <Q> to quit");
setcolor(BLUE);
setfillstyle(LINE_FILL,BLUE);

drawbg(bg,M,N,size,0,0);
setcolor(GREEN);
outtextxy(60,120,"PRESS KEY <1> :YOU ,");
outtextxy(70,150,"OTHER KEY :AUTOMATIC");
setcolor(WHITE);
x+=len;y+=len;
drawman(x,y,len);
x0=x;y0=y;
if((ch=getch())=='1'){
/* 人工控制 */
while((ch=getch())!='q'){
delay(800);
drawman(x,y,len);
switch(ch){
case 'a':
if(j>0&&bg[i][j-1]==0){
if(x>step){x-=step;j--;};
}
break;
case 's':
if(i<M-1&&bg[i+1][j]==0){
if(y<479-step){y+=step;i++;};
}
break;
case 'd':
if(j<N-1&&bg[i][j+1]==0){
if(x<639-step){x+=step;j++;}
}
break;
case 'w':
if(i>0&&bg[i-1][j]==0){
if(y>step){y-=step;i--;}
}
break;
default :break;
}
drawman(x,y,len);
if(i>=M-1&&j>=N-1){
settextstyle(4,0,3);
setcolor(RED);
outtextxy(150,260,"YOU WIN!");
}
setcolor(WHITE);
}
closegraph();
}/* 人工控制结束 */

else{
/* 电脑控制 */
/* direc表示上一步运动方向 */
/* 并表示下一步运动方向 */
/* 0~3分别表示 西、北、东、南 */

direc=2;
i=j=0;k=0;
while(i<M-1||j<N-1){
switch(direc){
case 0:
/* 以3,0,1,2的次序尝试 */
if(i<M-1&&bg[i+1][j]==0){
y+=step;i++;
direc=3;
}
else if(j>0&&bg[i][j-1]==0){
x-=step;j--;
direc=0;
}
else if(i>0&&bg[i-1][j]==0){
y-=step;i--;
direc=1;
}
else {
x+=step;j++;
direc=2;
}
p[k].x=x;
p[k].y=y;
p[k].direc=direc;
if(k>0){
count=k-1;
while(count>=0
&&(p[count].x!=p[k].x||p[count].y!=p[k].y))
count--;
if(count>=0){
k=count;
p[k].direc=direc;
i=(p[k].y-len)/step;
j=(p[k].x-len)/step;
}
}
k++;
break;
case 1:
if(j>0&&bg[i][j-1]==0){
x-=step;j--;
direc=0;
}
else if(i>0&&bg[i-1][j]==0){
y-=step;i--;
direc=1;
}
else if(j<N-1&&bg[i][j+1]==0){
x+=step;j++;
direc=2;
}
else{
y+=step;i++;
direc=3;
}
p[k].x=x;
p[k].y=y;
p[k].direc=direc;
if(k>0){
count=k-1;
while(count>=0
&&(p[count].x!=p[k].x||p[count].y!=p[k].y))
count--;
if(count>=0){
k=count;
p[k].direc=direc;
i=(p[k].y-len)/step;
j=(p[k].x-len)/step;
}
}
k++;
break;
case 2:
if(i>0&&bg[i-1][j]==0){
y-=step;i--;
direc=1;
}
else if(j<N-1&&bg[i][j+1]==0){
x+=step;j++;
direc=2;
}
else if(i<M-1&&bg[i+1][j]==0){
y+=step;i++;
direc=3;
}
else {
x-=step;j--;
direc=0;
}
p[k].x=x;
p[k].y=y;
p[k].direc=direc;
if(k>0){
count=k-1;
while(count>=0
&&(p[count].x!=p[k].x||p[count].y!=p[k].y))
count--;
if(count>=0){
k=count;
p[k].direc=direc;
i=(p[k].y-len)/step;
j=(p[k].x-len)/step;
}
}
k++;
break;
case 3:
if(j<N-1&&bg[i][j+1]==0){
x+=step;j++;
direc=2;
}
else if(i<M-1&&bg[i+1][j]==0){
y+=step;i++;
direc=3;
}
else if(j>0&&bg[i][j-1]==0){
x-=step;j--;
direc=0;
}
else {
y-=step;i--;
direc=1;
}
p[k].x=x;
p[k].y=y;
p[k].direc=direc;
if(k>0){
count=k-1;
while(count>=0
&&(p[count].x!=p[k].x||p[count].y!=p[k].y))
count--;
if(count>=0){
k=count;
p[k].direc=direc;
i=(p[k].y-len)/step;
j=(p[k].x-len)/step;
}
}
k++;
break;
default :break;
}

}
drawman(x0,y0,len);
for(i=0;i<k-1;i++){

drawman(p[i].x,p[i].y,len);
delay(80000);
drawman(p[i].x,p[i].y,len);
}
drawman(p[i].x,p[i].y,len);
/* printf("%6d\n",k);
for(i=0;i<k;i++){
printf("%6d\n",p[k].y*N+p[k].x);
if((k+1)%10==0)printf("\n");
}*/
getch();
closegraph();
}/* 电脑控制结束 */

}/* main()结束 */

/* 绘制小人 */
void drawman(int x,int y,int len){
int r=len/4;
rect(x-r,y-len,x+r,y-len+2*r);
line(x,y-len+2*r,x,y);
line(x-len,y,x+len,y);
line(x,y,x-len,y+len);
line(x,y,x+len,y+len);
}
/* 绘制迷宫地图 */
void drawbg(int bg[][N],int a,int b,int size,int x,int y){
int startx=x;
int i,j;
for(i=0;i<a;i++){
for(j=0;j<b;j++){
if(bg[i][j]==1)
rect(x,y,x+size-1,y+size-1);
x+=size;
}
x=startx;
y+=size;
}
rectangle(0,0,size*b,size*a);
line(0,0,size,0);line(0,0,0,size);
line(size*b,size*(a-1),size*b,size*a);
line(size*(b-1),size*a,size*b,size*a);
}
/* 绘制实心矩形 */
void rect(int x0,int y0,int x1,int y1){
int i,j;
for(i=x0;i<=x1;i++)
line(i,y0,i,y1);
}

/* 随机生成代表迷宫地图的数组 */
void makebg(int a,int b){
int i,j;
int ran;
int direc;
/* 初始化迷宫地图 */
for(i=0;i<a;i++)
for(j=0;j<b;j++)
bg[i][j]=1;

/* 随机生成迷宫通路 */
randomize();
i=j=0;direc=2;
while(1){

bg[i][j]=0;
if(i>=M-1&&j>=N-1)break;
ran=(int)rand()*4;
if(ran<1){
if(direc!=1&&i<a-1){
i++;
direc=3;
}
}
else if(ran<2){
if(direc!=2&&j>0){
j--;
direc=0;
}
}
else if(ran<3){
if(direc!=3&&i>0){
i--;
direc=1;
}
}
else {
if(direc!=0&&j<b-1){
j++;
direc=2;
}
}
}
/* 随机生成迷宫其余部分 */
for(i=0;i<a;i++)
for(j=0;j<b;j++)
if(bg[i][j]==1){
ran=(int)rand()*10;
if(ran<3)bg[i][j]=0;
}
}

热心网友 时间：2024-10-21 15:07

请把C++的注释风格改成风格的,两个程序都调试通过!
////////////////////////////////////////////////////////////////////////////////
程序1
#include<stdio.h>
#define
N1
11
#define
N2
10
int
getpath(int
maze[N1][N2])//在迷宫中探路的函数
{
int
stack[N1*N2][2];
int
i,x=1,y=1,ok,top=0;//可通路径上第一个点（入口点）的坐标进入路径数组stack
stack[top][0]=x;
stack[top][1]=y;//循环探路。加1则向前，减1则退回一步
while
(1)
{
ok=0;//标志能否向前
if
(maze[x][y+1]==0)
{y=y+1;ok=1;}//向右
else
if
(maze[x+1][y]==0)
{x=x+1;ok=1;}//向下
else
if
(maze[x][y-1]==0)
{y=y-1;ok=1;}//向左
else
if
(maze[x-1][y]==0)
{x=x-1;ok=1;}//向上
if
(!ok)//4方向均不通
{
top--;
if
(top==0)//栈空，无出路
{
printf("迷宫无出路\n");
return
0;
}
x=stack[top][0];//回退后路径上最后一个点的X坐标存入X
y=stack[top][1];//回退后路径上最后一个点的Y坐标存入Y
}
else//若能走通，
{
maze[x][y]=2;//将已经走过的点标记为2
top++;
stack[top][0]=x;//新进入的点的X坐标进入路径数组
stack[top][1]=y;//新进入的点的Y坐标进入路径数组
if
(x==N1-2&&y==N2-2)//到达出口
{
printf("路径为：\n");
for(i=0;i<top;i++)
{
printf("(%d,%d)-->",stack[i][0],stack[i][1]);
if((i+1)%5==0)
printf("\n");
}
printf("(%d,%d)\n",stack[top][0],stack[top][1]);
return
1;
}
}
}
}
void
printmaze(maze)//输出迷宫数组函数
int
maze[N1][N2];
{
int
i,j;
printf("迷宫数组为：\n");
for
(i=0;i<N1;i++)
{
for
(j=0;j<N2;j++)
printf("%2d",maze[i][j]);
printf("\n");
}
}
main()
{
int
A[N1][N2]=
{
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,1,1,
1,0,1,1,1,0,0,1,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,1,1,
1,0,1,1,1,1,0,0,1,1,
1,1,1,0,0,0,1,0,1,1,
1,1,1,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1};
printmaze(A);
getpath(A);
}
//////////////////////////////////////////////////////////////////////
程序2
#include<stdio.h>
#include<stdlib.h>
#define
OVERFLOW
-1
#define
MAX
100
#define
N
11
typedef
struct
{
int
x;
int
y;
int
d;
}Data;
typedef
struct
{
int
pos;
Data
data[MAX];
}SNode,*Stack;
Stack
InitStack()
{
Stack
pStack;
pStack=(Stack)malloc(sizeof(SNode));
if(!pStack)
exit(OVERFLOW);
pStack->pos=-1;
return
pStack;
}
int
IsEmpty(Stack
stack)
{
return
stack->pos==-1;
}
void
Push(Stack
pStack,Data
x)
{
if(pStack->pos>=MAX-1)
exit(OVERFLOW);
else
{
pStack->pos++;
pStack->data[pStack->pos]=x;
}
}
void
Pop(Stack
pStack)
{
if(pStack->pos==-1)
exit(OVERFLOW);
else
pStack->pos--;
}
Data
GetTop(Stack
pStack)
{
return
pStack->data[pStack->pos];
}
Data
SetStackElem(int
x,int
y,int
d)
{
Data
element;
element.x=x;
element.y=y;
element.d=d;
return
element;
}
void
DisplayPath(Stack
pStack)
{
Data
element;
printf("The
path
is:\n");
while(!IsEmpty(pStack))
//多了个;
{
element=GetTop(pStack);
Pop(pStack);
printf("The
node
is:
%d
%d\n",element.x,element.y);
}
}
void
MazePath(int
maze[][N],int
direction[][2],int
x1,int
y1,int
x2,int
y2)
{
int
i,j,k,g,h;
Stack
pStack;
Data
element;
pStack=InitStack();
maze[x1][y1]=2;
Push(pStack,SetStackElem(x1,y1,0));
while(!IsEmpty(pStack))//以前多了一个;
{
element=GetTop(pStack);
Pop(pStack);
i=element.x;
j=element.y;
k
=
element.d;
while
(k<=3)//用while
{
g=i+direction[k][0];
h=j+direction[k][1];
if(g==x2&&h==y2&&maze[g][h]==0)
{
Push(pStack,SetStackElem(i,j,k));//把路径上最后一个点放入
DisplayPath(pStack);
return;//怎么会有返回值?
}
if(maze[g][h]==0)
{
maze[g][h]=2;
Push(pStack,SetStackElem(i,j,k+1));
i=g;
j=h;
k=0;
}
else
k++;
}
}
printf("The
path
has
not
been
found\n");
}
void
main()
{
int
direction[][2]={0,1,1,0,0,-1,-1,0};
int
maze[][N]=
{
1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1
};
MazePath(maze,direction,1,1,6,9);
}

声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com