📄 subject_47820.htm
字号:
<p>
序号：47820 发表者：最后一根稻草 发表日期：2003-07-24 16:11:44
<br>主题：请教迷宫问题的源代码
<br>内容：最近忽然想起了以前在哪本书上看过有关的迷宫问题，可惜没不懂，现在想重新研究一下，哪位高手能够告诉我它的算法和C语言的源程序，不胜感激。
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：hhua 回复日期：2003-07-25 00:13:55
<br>内容：迷宫问题主要是“队列”的使用，比如求迷宫出口个入口之间的最短路径问题，源程序在附带文件中；<BR> GetPatch.c是源代码；<BR> Input.txt为迷宫的描述，第一行表示迷宫有多少行，多少列，下面就是迷宫的描述数据，1表示通路，0表示障碍物（不通）。程序根据次迷宫描述文件寻求入口到出口之间的最段路径（入口和出口默人为左上角和右下角）。本题目定义在一个点向8个方向移动。<BR> output.txt为路径的显示输出文件，算法非常简单，主要就是队列的应用。<BR><BR><BR>GetPath.c<BR><BR>/**************************************************************************\<BR>* Function : Get short path in mi gong *<BR>* Paraneters: Input file about mi gong *<BR>* The format of input file: *<BR>* First line is heigh and width,Follow are migong data *<BR>* 1 means can run , 0 means fraise *<BR>* examp: *<BR>* 6,8 *<BR>* 1,0,0,0,1,0,0,0 *<BR>* 0,1,0,1,0,1,0,0 *<BR>* 1,0,1,1,0,0,0,0 *<BR>* 1,0,0,0,1,1,0,0 *<BR>* 0,1,1,0,0,1,1,1 *<BR>* 1,0,0,1,1,0,0,1 *<BR>* *<BR>* Return : None *<BR>* Writer : James Lee 2001.04.24 *<BR>* Remark : Modify By James Lee on 2001.04.24 *<BR>\**************************************************************************/<BR><BR># include "iostream.h"<BR># include "process.h"<BR># include "stdlib.h"<BR># include "stdio.h"<BR># include "string.h"<BR><BR>typedef struct<BR>{<BR> int x;<BR> int y;<BR> int Prev;<BR>}QUEUE;<BR><BR>typedef struct<BR>{<BR> int x;<BR> int y;<BR>}MOVE;<BR><BR>int ReadData(int *MiGong,FILE *InFile,int Height,int Width);<BR><BR>int main(int argc,char *argv[])<BR>{<BR> FILE *InFile,*OutFile;<BR> unsigned char Buffer[80],*Ptr=NULL;<BR> int *MiGong=NULL;<BR> int Height,Width,i,j,k,ret,Front,Rear;<BR> QUEUE *Queue=NULL;<BR> MOVE Move[8]=<BR> {<BR> { 0,-1},<BR> { 1,-1},<BR> { 1, 0},<BR> { 1, 1},<BR> { 0, 1},<BR> {-1, 1},<BR> {-1, 0},<BR> {-1,-1},<BR> };<BR><BR><BR> if (argc!=3)<BR> {<BR> cout<<endl<<"Command_line error!";<BR> cout<<endl<<"Usage: GetPath.exe InputFile OutputFile";<BR> exit(1);<BR> }<BR><BR> InFile=fopen(argv[1],"rb");<BR> if (InFile==NULL)<BR> {<BR> cout<<endl<<"Input File "<<argv[1]<<" can't open!";<BR> exit (2);<BR> }<BR><BR> OutFile=fopen(argv[2],"wb");<BR> if (OutFile==NULL)<BR> {<BR> cout<<endl<<"Output File "<<argv[2]<<" can't create!";<BR> exit (2);<BR> }<BR><BR> memset(Buffer,0,sizeof(unsigned char)*20);<BR> fgets(Buffer,20,InFile);<BR> Ptr=Buffer;<BR> while(*Ptr!=',')<BR> Ptr++;<BR><BR> *(Ptr++)=0;<BR> Height=atoi(Buffer);<BR> Width=atoi(Ptr);<BR> Width+=2;<BR> Height+=2;<BR> MiGong=(int*)malloc(Height*Width*sizeof(int));<BR> if (MiGong==NULL)<BR> {<BR> cout<<endl<<"Not enough memory!";<BR> exit (3);<BR> }<BR> memset(MiGong,0,Height*Width*sizeof(int));<BR> ret=ReadData(MiGong,InFile,Height,Width);<BR> if (ret!=0)<BR> {<BR> if (ret==1)<BR> {<BR> sprintf(Buffer,"Input file data format error: Height mismatch In fact!%c%c",13,10);<BR> cout<<Buffer;<BR> fwrite(Buffer,strlen(Buffer),1,OutFile);<BR> free(MiGong);<BR> exit (4);<BR> }<BR> if (ret==2)<BR> {<BR> sprintf(Buffer,"Input file data format error: Width mismatch In fact!%c%c",13,10);<BR> cout<<Buffer;<BR> fwrite(Buffer,strlen(Buffer),1,OutFile);<BR> free(MiGong);<BR> exit (5);<BR> }<BR> if (ret==3)<BR> {<BR> sprintf(Buffer,"Input file data format error: None Number between two dot character",13,10);<BR> cout<<Buffer;<BR> fwrite(Buffer,strlen(Buffer),1,OutFile);<BR> free(MiGong);<BR> exit (6);<BR> }<BR> if (ret==4)<BR> {<BR> sprintf(Buffer,"Input file data format error: None dot between two number character%c%c",13,10);<BR> cout<<Buffer;<BR> fwrite(Buffer,strlen(Buffer),1,OutFile);<BR> free(MiGong);<BR> exit (7);<BR> }<BR> }<BR><BR> Queue=(QUEUE*)malloc(Width*Height*8*sizeof(QUEUE));<BR> if (Queue==NULL)<BR> {<BR> cout<<endl<<"Not enough memory for Queue!";<BR> free(MiGong);<BR> exit(8);<BR> }<BR> memset(Queue,0,Width*Height*8*sizeof(QUEUE));<BR><BR> i=Height-2;j=Width-2;<BR> if (MiGong[i*Width+j]==1)<BR> {<BR> MiGong[i*Width+j]=-1;<BR> ret=1;<BR> }<BR> else<BR> ret=-1;<BR><BR> if (ret==1)<BR> {<BR> Front=0;<BR> Rear=0;<BR> Queue[Front].x=j;<BR> Queue[Front].y=i;<BR> Queue[Front].Prev=-1;<BR> ret=0;<BR> while(1)<BR> {<BR> if (Front>Rear)<BR> {<BR> ret=-1;<BR> break;<BR> }<BR><BR> for (k=0;k<8;k++)<BR> {<BR> i=Queue[Front].y;<BR> j=Queue[Front].x;<BR> i+=Move[k].y;<BR> j+=Move[k].x;<BR> if (MiGong[i*Width+j]==1)<BR> {<BR> Rear++;<BR> Queue[Rear].x=j;<BR> Queue[Rear].y=i;<BR> Queue[Rear].Prev=Front;<BR> MiGong[i*Width+j]=-1;<BR> if (i==1 && j==1)<BR> {<BR> ret=1;<BR> break;<BR> }<BR> }<BR> }<BR> if (ret==1)<BR> break;<BR><BR> Front++;<BR> }<BR> }<BR><BR> if (ret==1)<BR> {<BR> for (i=0;i<Height;i++)<BR> {<BR> for (j=0;j<Width;j++)<BR> {<BR> if (MiGong[i*Width+j]==-1)<BR> MiGong[i*Width+j]=1;<BR> }<BR> }<BR> sprintf(Buffer,"%20s%10s%c%c","Line","Col",13,10);<BR> cout<<endl<<Buffer;<BR> fwrite(Buffer,strlen(Buffer),1,OutFile);<BR> k=1;<BR> while(1)<BR> {<BR> sprintf(Buffer,"Step%5d:%9d%10d%c%c",k,Queue[Rear].y,Queue[Rear].x,13,10);<BR> k++;<BR> cout<<Buffer;<BR> fwrite(Buffer,strlen(Buffer),1,OutFile);<BR> if (Rear==0)<BR> break;<BR><BR> Rear=Queue[Rear].Prev;<BR> }<BR> }<BR> else<BR> {<BR> sprintf(Buffer,"Not Path to exit!");<BR> cout<<endl<<Buffer<<endl;<BR> fwrite(Buffer,strlen(Buffer),1,OutFile);<BR> }<BR><BR> free(MiGong);<BR> free(Queue);<BR> fcloseall();<BR> return 0;<BR>}<BR><BR>/**************************************************************************\<BR>* Function : Read Data of MiGong from Input File *<BR>* Paraneters: MiGong ---MiGong array *<BR>* 8InFile---Input File Pointer *<BR>* Return : 0,Read Success *<BR>* 1,Read Fail,Height error 2,Read fail, Width error *<BR>* Writer : Li XueHui *<BR>* Date : 2000.12.14 *<BR>* Modify : 2000.12.14 By Li XueHui *<BR>\**************************************************************************/<BR>int ReadData(int *MiGong,FILE *InFile,int Height,int Width)<BR>{<BR> int i,j;<BR> unsigned char ch,Flag,LFFlag;<BR><BR> i=1;j=1;<BR> LFFlag=0;<BR> Flag=0;<BR> while(1)<BR> {<BR> fread(&ch,1,1,InFile);<BR> if (feof(InFile))<BR> {<BR> if (LFFlag==1)<BR> i++;<BR> break;<BR> }<BR><BR> if (ch==',')<BR> {<BR> if (Flag==',')<BR> {<BR> Flag=0;<BR> continue;<BR> }<BR> else<BR> return 3; // error , two ','<BR> }<BR><BR> if (ch==0x0D)<BR> {<BR> fseek(InFile,1,SEEK_CUR);<BR> Flag=0;<BR> LFFlag=0;<BR> i++;<BR> if (j!=Width-1)<BR> return 2;<BR> j=1;<BR> continue;<BR> }<BR><BR> if (ch>=0x30 && ch<=0x39)<BR> {<BR> if (Flag==',')<BR> return 4;<BR> else<BR> Flag=',';<BR><BR> if (i>Height-2)<BR> return 1;<BR><BR> if (j>Width-2)<BR> return 2;<BR><BR> ch-=0x30;<BR> MiGong[i*Width+j]=ch;<BR> j++;<BR> if (j>Height-2)<BR> LFFlag=1;<BR> }<BR> }<BR> if (i!=Height-1)<BR> return 1;<BR><BR> return 0;<BR>}<BR><BR>Input.txt<BR><BR>6,8<BR>1,1,1,1,1,1,0,1,<BR>0,0,0,0,0,1,0,1<BR>1,0,0,1,0,0,1,1<BR>1,0,0,0,1,1,0,1<BR>1,0,0,0,0,0,0,1<BR>1,1,1,1,1,1,0,1<BR><BR>Output.txt<BR><BR> Line Col<BR>Step 1: 1 1<BR>Step 2: 1 2<BR>Step 3: 1 3<BR>Step 4: 1 4<BR>Step 5: 1 5<BR>Step 6: 2 6<BR>Step 7: 3 7<BR>Step 8: 4 8<BR>Step 9: 5 8<BR>Step 10: 6 8<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：最后一根稻草 回复日期：2003-07-29 09:22:05
<br>内容：感谢lixuehui的帮助，可惜程序太大，我一时看不明白，只知大概分为这样几个部分，数据输入部分，数据输出部分，数据处理部分，而且考虑得非常周到，几乎所有的错误可能都想到了，实在是一个好程序。希望看到后能多加一些说明，使我能深入理解。新近我看到了一个小程序，稍加修改也能完成类似功能。<BR><BR>// 迷宫问题（递归求解）.cpp : Defines the entry point for the console application.<BR>//<BR><BR>#include "stdafx.h"<BR># include "iostream.h"<BR># include "process.h"<BR># include "stdlib.h"<BR># include "stdio.h"<BR># include "string.h"<BR>const m=4;<BR>const p=7;<BR> typedef struct offsets{<BR> int a,b;<BR> char *dir;<BR>}MOVE;<BR><BR>MOVE move[8]=<BR> {<BR> {-1,0,"N"},<BR> {-1,1,"NE"},<BR> {0,1,"E"},<BR> {1,1,"SE"},<BR> {1,0,"S"},<BR> {1,-1,"SW"},<BR> {0,-1,"W"}, <BR> {-1,-1,"NW"},<BR> };<BR><BR>int maze[6][8]=<BR>{<BR> {1,1,1,1,1,1,1,1},<BR> {0,1,0,1,0,1,0,1},<BR> {0,1,1,1,0,0,0,1},<BR> {1,0,0,0,1,1,0,1},<BR> {1,1,1,0,0,1,1,0},<BR> {1,1,1,1,1,1,1,1},<BR>};<BR><BR>int mark[6][8]=/////标志数组，若此路线走过则标示为1，下次不可再走<BR>{<BR> {0,0,0,0,0,0,0,0},<BR> {0,0,0,0,0,0,0,0},<BR> {0,0,0,0,0,0,0,0},<BR> {0,0,0,0,0,0,0,0},<BR> {0,0,0,0,0,0,0,0},<BR> {0,0,0,0,0,0,0,0},<BR>};<BR><BR><BR><BR>int seekpath(int x,int y)//从迷宫某一位置[x][y]开始，寻找通向出口[m][p]的一条路径。如果找到<BR>{ //则函数返回1。否则函数返回0。试探的出发点为[1][0]<BR><BR> int i,g,h;//用g,h记录位置信息 <BR> char *d;////用d记录方向<BR> if(x==m && y==p)return 1;//已达到出口，返回1 <BR> for(i=0;i<8;i++)///////////依次对每一个方向寻找通向出口的路径<BR> {<BR> g=x+move[i].a;<BR> h=y+move[i].b;<BR> d=move[i].dir;//找下一个位置和方向（g,h,dir)<BR> if(maze[g][h]==0 && mark[g][h]==0)///////////下一位置可通，试探该方向<BR> {////<BR> mark[g][h]=1;//标记为已访问过<BR> <BR> <BR> if(seekpath(g,h))<BR> {<BR> //试探成功，逆向输出路径坐标<BR> <BR> <BR> cout<<"("<<g<<","<<h<<"),"<<"\n"<<"Direction： "<<d<<","<<"\n";<BR> return 1;<BR> }<BR> }<BR> //回溯，换一个方向再试探通向出口的路径<BR> }<BR> if(x==1 && y==1)cout<<"no path in maze"<<endl;<BR> return 0;<BR>}<BR>int main(int argc, char* argv[])<BR>{<BR> seekpath(1,0);<BR> <BR> return 0;<BR>}<BR>
<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -