高分跪求c++迷宫求解问题 （要用深度优先和广度优先两种方法）
RT
现有一个M*N的迷宫，迷宫的地图用二维数组存储。其中，0表示此顶点可以通过，1表示不能通过。试编程找到从任意一点(x1,y1)到任意一点(x2,y2)的【最短】路径。
路径不要直接输出，要先用一种结构把它存起来，找到最短路径后，再一起输出。
P.S.
M,N是变量。
要用深度优先和广度优先两种方法实现。
找到的那条路径一定是最短的。
以左上角为原点，右下角坐标为(M,N)
有代码＋较为详尽的注释者，另有加分！
急求，在线等！！！
回一楼，我要C++的，不是C的。。
能帮忙把注释改成中文的嘛？英文的看不太懂。。
很久以前做的，现在都忘记了。你看一下吧。我的报告，也可以发给你，不过还是期望你自己可以学会怎么做，少年智则国智。C＋＋和C一回事，你把其中的语法规则改一下就好，比如输入输出语句，将结构体改成类，也可不改，都支持的。
#include "stdio.h"
#include "conio.h" /*provide the support of getch */
#define max 10
#define maxlength (max*max) /*the max lenth of the path*/
#define zdir 4 /*the total direction*/
#include "graphics.h" /*provide the support of graphics*/
#include "dos.h" /* provide the support of function:sleep */
#include "time.h" /* provide the support of sleep */
#define M 10 /*the max lenth of the map*/
#define N 10 /*the max lenth of the map*/
/*the following four function are stating functions*/
void printmap(void);
int zfindpath(int row,int col,int erow,int ecol);
void creategraphich(int n1,int n2,int n3,int n4);
void creategraphich(int n1,int n2,int n3,int n4);
int zmap[max][max]={ {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}
};
struct {
int row,col;
}offsets[zdir]={{0,1 },
{1,0 },
{0,-1},
{-1,0}
};
struct {
int row;
int col;
} path[maxlength];
/*define a globle variable to convenience output*/
int len;
int zfindpath(int row,int col,int erow,int ecol)
{
int dir,row2,col2;
/* int x=150+col*22,y=100+row*22; */
sleep(1);
setcolor(10); /* draw a cirlce */
setfillstyle(1, 14);
circle(150+(col)*22+10,100+(row)*22+10, 8);
floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10);
if((row==erow)&&(col==ecol))
{ path[0].row=erow;
path[0].col=ecol; /* judge if is the exit */
return 1;
} /* the end of if */
zmap[row][col]=2; /* block current position */
for(dir=0;dir<zdir;dir++)
{
row2=row+offsets[dir].row; /* step to next space */
col2=col+offsets[dir].col;
if(zmap[row2][col2]==0) /* mean the way could go at this stage */
{
len=zfindpath(row2,col2,erow,ecol);
if(len>0)
{
path[len].row=row2; /* use recursion to find the path */
path[len].col=col2;
return ++len;
} /*the end of if */
} /*the end of if */
} /* the end of for */
sleep(1);
setfillstyle(1, 15);
bar( 150+col*22,100+row*22,170+col*22,120+row*22);
/* sleep(1); */
return 0;
} /* the end of zfindpaht */
void printmap() /* first ,print the map that we will go */
{
int i,j;
for(i=0;i<max;i++)
{
for(j=0;j<max;j++)
printf(" %d",zmap[i][j]);
printf("\n");
}
getch();
}
void createmap(int n1,int n2,int n3,int n4)
{
int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;
void *buf;
int gdriver=DETECT,gmode=VGAHI;
initgraph(&gdriver,&gmode,"c:\\tc");
cleardevice();
setbkcolor(10);
setcolor(1);
settextstyle(4, 0, 5);
outtextxy(70,20,"hello,welcome to here! ");
setcolor(4);
setfillstyle(1, 4);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
}
line(100,80,150+n2*22,100+n1*22); /* draw a line */
line(337+(n4-8)*22,287+(n3-8)*22,337,360);
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(80,60,"this is the entrance! ");
outtextxy(320,360,"this is the exit! ");
}
void creategraphich(int n1,int n2,int n3,int n4)
{
int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;
void *buf;
int gdriver=DETECT,gmode=VGAHI;
initgraph(&gdriver,&gmode,"c:\\tc");
cleardevice();
setbkcolor(10);
setcolor(1);
settextstyle(4, 0, 5);
outtextxy(70,20,"hello,welcome to here! ");
setcolor(4);
setfillstyle(1, 4);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
}
line(100,80,150+n2*22,100+n1*22); /* draw a line */
line(337+(n4-8)*22,287+(n3-8)*22,337,360);
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(80,60,"this is the entrance! ");
outtextxy(320,360,"this is the exit! ");
setcolor(4); /* draw a circle heart */
setfillstyle(1, 4);
sector(250,350,0,180,20,20); /* draw the upper circle */
sector(290,350,0,180,20,20); /* draw the downer circle */
sector(310,350,180,240,80,76);
sector(230,350,300,360,80,76);
setcolor(10); /* draw a cirlce */
setfillstyle(1, 14);
circle(150+(n2)*22+10,100+(n1)*22+10, 8);
floodfill(150+(n2)*22+10+4, 100+(n1)*22+10+4, 10);
size=imagesize(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8);
buf=malloc(size);
getimage(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8,buf);
/*sleep(2);
putimage(192,122 , buf, COPY_PUT); */
for(i=len;i>0;i--) /* the total number of the path is len-1 */
{
trow=path[i-1].row-path[i].row;
tcol=path[i-1].col-path[i].col;
sleep(1);
x=x+tcol*22;
y=y+trow*22;
putimage(x,y, buf, COPY_PUT);
}
/* printf the result*/
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(357,287,"sussessfully!!!");
getch();
closegraph();
free((void *)buf);
}
void changemap(int d)
{
FILE *fw;
int i,j;
if(d==1)
{
fw=fopen("c:\\tc\\a.txt","r");
if(!fw) {printf("not found!"); getch();return;}
for(i=0;i<M;i++)
{ for( j=0;j<N;j++ ) { fscanf(fw,"%d",&zmap[i][j]);}
} /* the end of for */
}/* the end of first if*/
else {
fw=fopen("c:\\tc\\b.txt","r");
if(!fw) {printf("not found!"); getch();return;}
for(i=0;i<M;i++)
{ for( j=0;j<N;j++ ) { fscanf(fw,"%d",&zmap[i][j]);}
} /* the end of for */
} /* the end of else */
printf("the map we will follow to search :\n");
for(i=0;i<M;i++)
{ for(j=0;j<N;j++) { printf(" %d",zmap[i][j]);}
printf("\n");
}
getch();
fclose(fw);
}
main()
{
while(1){
int i,j,n1,n2,n3,n4,n5,n6;
int zch;
/* while(1){ */
len=0;
printf("if you want to use the default map,press 1,if you want to use the spare map,press 2 :\n");
scanf("%d",&zch);
if(zch==2)
changemap(1);
/*printmap(); */
else
{
changemap(2);
/* printmap(); */ /* first ,print the map that we will go */
}
printf("please input the startpoint(row,col):\n"); /* input the start point and end point ,those two value should less then 10 and larger then 0*/
scanf("%d%d",&n1,&n2);
printf("please input the endpoint(row,col):\n");
scanf("%d%d",&n3,&n4);
n5=n1;
n6=n2;
createmap(n5,n6,n3,n4); /* in this step ,we will create the primitive map */
zfindpath(n1,n2,n3,n4); /* function of searching the path */
path[len].row=n5;
path[len].col=n6;
getch();
closegraph();
printf("the resultant path is \n");
for(i=len;i>0;i--)
{
printf("(%d,%d)\n",path[i].row,path[i].col);
} /* the end of for*/
getch();
printf("now,we will create the final graphics of the map:\n"); /* create the final graphics of the map*/
getch();
creategraphich(n5,n6,n3,n4);
} /* the end of while */
} /* the end of main */
#include "stdio.h"
#include "conio.h" /*provide the support of getch */
#define max 10
#define maxlength (max*max) /*the max lenth of the path*/
#define zdir 4 /*the total direction*/
#include "graphics.h" /*provide the support of graphics*/
#include "dos.h" /* provide the support of function:sleep */
#include "time.h" /* provide the support of sleep */
#define M 10 /*the max lenth of the map*/
#define N 10 /*the max lenth of the map*/
/*the following four function are stating functions*/
void printmap(void);
int zfindpath(int row,int col,int erow,int ecol);
void creategraphich(int n1,int n2,int n3,int n4);
void creategraphich(int n1,int n2,int n3,int n4);
int zmap[max][max]={ {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}
};
struct {
int row,col;
}offsets[zdir]={{0,1 },
{1,0 },
{0,-1},
{-1,0}
};
struct {
int row;
int col;
} path[maxlength];
/*define a globle variable to convenience output*/
int len;
int zfindpath(int row,int col,int erow,int ecol)
{
int dir,row2,col2;
/* int x=150+col*22,y=100+row*22; */
sleep(1);
setcolor(10); /* draw a cirlce */
setfillstyle(1, 14);
circle(150+(col)*22+10,100+(row)*22+10, 8);
floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10);
if((row==erow)&&(col==ecol))
{ path[0].row=erow;
path[0].col=ecol; /* judge if is the exit */
return 1;
} /* the end of if */
zmap[row][col]=2; /* block current position */
for(dir=0;dir<zdir;dir++)
{
row2=row+offsets[dir].row; /* step to next space */
col2=col+offsets[dir].col;
if(zmap[row2][col2]==0) /* mean the way could go at this stage */
{
len=zfindpath(row2,col2,erow,ecol);
if(len>0)
{
path[len].row=row2; /* use recursion to find the path */
path[len].col=col2;
return ++len;
} /*the end of if */
} /*the end of if */
} /* the end of for */
sleep(1);
setfillstyle(1, 15);
bar( 150+col*22,100+row*22,170+col*22,120+row*22);
/* sleep(1); */
return 0;
} /* the end of zfindpaht */
void printmap() /* first ,print the map that we will go */
{
int i,j;
for(i=0;i<max;i++)
{
for(j=0;j<max;j++)
printf(" %d",zmap[i][j]);
printf("\n");
}
getch();
}
void createmap(int n1,int n2,int n3,int n4)
{
int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;
void *buf;
int gdriver=DETECT,gmode=VGAHI;
initgraph(&gdriver,&gmode,"c:\\tc");
cleardevice();
setbkcolor(10);
setcolor(1);
settextstyle(4, 0, 5);
outtextxy(70,20,"hello,welcome to here! ");
setcolor(4);
setfillstyle(1, 4);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
}
line(100,80,150+n2*22,100+n1*22); /* draw a line */
line(337+(n4-8)*22,287+(n3-8)*22,337,360);
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(80,60,"this is the entrance! ");
outtextxy(320,360,"this is the exit! ");
}
void creategraphich(int n1,int n2,int n3,int n4)
{
int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;
void *buf;
int gdriver=DETECT,gmode=VGAHI;
initgraph(&gdriver,&gmode,"c:\\tc");
cleardevice();
setbkcolor(10);
setcolor(1);
settextstyle(4, 0, 5);
outtextxy(70,20,"hello,welcome to here! ");
setcolor(4);
setfillstyle(1, 4);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
}
line(100,80,150+n2*22,100+n1*22); /* draw a line */
line(337+(n4-8)*22,287+(n3-8)*22,337,360);
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(80,60,"this is the entrance! ");
outtextxy(320,360,"this is the exit! ");
setcolor(4); /* draw a circle heart */
setfillstyle(1, 4);
sector(250,350,0,180,20,20); /* draw the upper circle */
sector(290,350,0,180,20,20); /* draw the downer circle */
sector(310,350,180,240,80,76);
sector(230,350,300,360,80,76);
setcolor(10); /* draw a cirlce */
setfillstyle(1, 14);
circle(150+(n2)*22+10,100+(n1)*22+10, 8);
floodfill(150+(n2)*22+10+4, 100+(n1)*22+10+4, 10);
size=imagesize(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8);
buf=malloc(size);
getimage(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8,buf);
/*sleep(2);
putimage(192,122 , buf, COPY_PUT); */
for(i=len;i>0;i--) /* the total number of the path is len-1 */
{
trow=path[i-1].row-path[i].row;
tcol=path[i-1].col-path[i].col;
sleep(1);
x=x+tcol*22;
y=y+trow*22;
putimage(x,y, buf, COPY_PUT);
}
/* printf the result*/
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(357,287,"sussessfully!!!");
getch();
closegraph();
free((void *)buf);
}
void changemap(int d)
{
FILE *fw;
int i,j;
if(d==1)
{
fw=fopen("c:\\tc\\a.txt","r");
if(!fw) {printf("not found!"); getch();return;}
for(i=0;i<M;i++)
{ for( j=0;j<N;j++ ) { fscanf(fw,"%d",&zmap[i][j]);}
} /* the end of for */
}/* the end of first if*/
else {
fw=fopen("c:\\tc\\b.txt","r");
if(!fw) {printf("not found!"); getch();return;}
for(i=0;i<M;i++)
{ for( j=0;j<N;j++ ) { fscanf(fw,"%d",&zmap[i][j]);}
} /* the end of for */
} /* the end of else */
printf("the map we will follow to search :\n");
for(i=0;i<M;i++)
{ for(j=0;j<N;j++) { printf(" %d",zmap[i][j]);}
printf("\n");
}
getch();
fclose(fw);
}
main()
{
while(1){
int i,j,n1,n2,n3,n4,n5,n6;
int zch;
/* while(1){ */
len=0;
printf("if you want to use the default map,press 1,if you want to use the spare map,press 2 :\n");
scanf("%d",&zch);
if(zch==2)
changemap(1);
/*printmap(); */
else
{
changemap(2);
/* printmap(); */ /* first ,print the map that we will go */
}
printf("please input the startpoint(row,col):\n"); /* input the start point and end point ,those two value should less then 10 and larger then 0*/
scanf("%d%d",&n1,&n2);
printf("please input the endpoint(row,col):\n");
scanf("%d%d",&n3,&n4);
n5=n1;
n6=n2;
createmap(n5,n6,n3,n4); /* in this step ,we will create the primitive map */
zfindpath(n1,n2,n3,n4); /* function of searching the path */
path[len].row=n5;
path[len].col=n6;
getch();
closegraph();
printf("the resultant path is \n");
for(i=len;i>0;i--)
{
printf("(%d,%d)\n",path[i].row,path[i].col);
} /* the end of for*/
getch();
printf("now,we will create the final graphics of the map:\n"); /* create the final graphics of the map*/
getch();
creategraphich(n5,n6,n3,n4);
} /* the end of while */
} /* the end of main */
温馨提示：内容为网友见解，仅供参考
无其他回答
高分跪求c++迷宫求解问题 (要用深度优先和广度优先两种方法)
其中,0表示此顶点可以通过,1表示不能通过。试编程找到从任意一点(x1,y1)到任意一点(x2,y2)的【最短】路径。路径不要直接输出,要先用一种结构把它存起来,找到最短路径后,再一起输出。P.S.M,N是变量。要用深度优先和广度优先两种方法实现。找到的那条路径一定是最短的。以左上角为原点,右下角坐标为(M,...
走迷宫的原理
1. 深度优先搜索（DFS）：DFS 是一种基于递归的搜索策略，其原理是从起点开始，沿着一条路径不断向迷宫深处探索，直到无法继续前进为止。此时，回溯到上一步并尝试其他可能的路径。DFS 算法在搜索过程中不关心路径的长短，因此在解决迷宫问题时可能会导致非最短路径。2. 广度优先搜索（BFS）：BFS 是一...
进行DFSS可以带来哪些好处?
1. 提高产品质量：DFSS强调设计的重要性，而良好的设计可以大大提高产品质量。通过在设计阶段就考虑所有可能的因素，可以确保产品在制造和使用过程中表现出色。2. 降低成本：DFSS通过优化设计来降低制造成本。通过减少材料、能源和劳动力，可以显著降低生产成本。3. 缩短上市时间：通过优化设计，DFSS可以减少产...
相似回答
