迷宫的路由与生成课程设计说明书数据结构与算法设计综合设计

课程设计说明书课程名称数据结构与算法设计综合设计课程代码题目迷宫的生成与路由年级/专业/班学生姓名学号开始时间年月日完成时间年月日课程设计成绩平时学习态度与效果（30）技术水平与实际能力（30）团队协作与技术创新（10分）设计说明书撰写质量（30）总分（100）指导教师签名年月日目录1需求分析12概要设计33详细设计94调试分析205用户使用说明226测试结果247结论26致谢29参考文献30摘要用C语言编写的生成一个NMN行M列的迷宫，完成迷宫的组织和存储，并实现迷宫路由算法。（1）使用二维数组MATRIXMN表示迷宫，其中M,N为迷宫的行、列数，当元素值为0时表示该点是通路，当元素值为1时表示该点是墙。在每一点都有4种方向可以走，可以用数组WALL4来表示每一个方向上的墙，用另一个二维数组GRAPHMN记录墙和节点的情况。（2）选用深度优先算法和广度优先算法寻找路径，迷宫由程序自动创建。关键词迷宫生成、广度优先、深度优先引言1需求分析设计算法生成一个NM（N行M列）的迷宫，并完成迷宫的组织和储存。实现两种不同的迷宫算法广度优先，深度优先算法。要求1N和M是用户可配置的，缺省值为50和50。2迷宫的入口和出口分别在第0行和第N1行上，随机选择。3生成迷宫要求是随机，且连通的。4迷宫具有多条分支路线。5进行深度优先探索迷宫路径并进行输出。6进行广度优先探索迷宫路径并进行输出。7实现图形化界面显示。8在图形界面输出寻路过程坐标。8实现按钮事件处理的图形用户界面交互。11任务与分析随机生成一个迷宫（由用户规定其大小）并使用。算法分析迷宫是连通的。使用图形表示，并分别在迷宫的第一行和最后一行随机选择出口和入口，输出可通迷宫的最佳路径。任务一迷宫随机生成算法的实现。任务二迷宫深度优先搜索算法实现。任务三迷宫广度优先搜索算法实现。任务三进行图形界面的表示。分析对三大主要功能模块进行三大主类设计，分别为MAZE类，DFS类，BFS类，最后使用MFC应用程序进行图形界面的表示。12测试数据M,N取默认值50，50M,N取默认值20，20M,N取默认值60,602概要设计（此处说明本课程设计题目的模块划分及各模块的功能介绍和对应的函数名（原型）以及各模块间的层次（调用）关系以框图描述）1本系统所设计的函数见表21MAZECELL类函数名称函数原型功能描述MAZECELLMAZECELL迷宫格对象初始化。MAZE类函数名称函数原型功能描述MAZEMAZEINTM49,INTN49初始化迷宫行数和列数，构造节点矩阵CREATEMAZEVOIDCREATEMAZE随机创建课连通迷宫PRINTMAZEVOIDPRINTMAZE在DOS界面打印迷宫HASUNACCESSADJNODEBOOLHASUNACCESSADJNODEINT,INT判断下一节点是否可以访问BREAKWALLVOIDBREAKWALLMAZECELL拆掉墙，使两节点连通TONEXTNODEVOIDTONEXTNODE移动当前节点到下一节点MAKEROMDANSTARTANDENDVOIDMAKEROMDANSTARTANDEND随机生成入口和出口GETGRAPHROWINTGETGRAPHROW返回迷宫矩阵的行数GETGRAPHCOLUMNINTGETGRAPHCOLUMN返回迷宫矩阵的列数MAZEMAZE销毁迷宫，释放内存GETGRAPHINTGETGRAPH返回迷宫的矩阵数组COORDINATE类函数名称函数原型功能描述COORDINATECOORDINATEINT,INTCOORDINATE对象手动初始化以及默认初始化GETXINTGETX获得坐标X值GETYINTGETY获得坐标Y值DFS类函数名称函数原型功能描述DFSDFSINTGRAPH,INT,INTDFS对象初始化MAZEPATHVOIDMAZEPATHDFS算法寻找生成迷宫路径HASPATHBOOLHASPATHINTX,INTY有可访问迷宫格判断PRINTPATHVOIDPRINTPATHDOS界面打印路径GETVALUEINTGETVALUEINT,INT获得DFS对象某个迷宫格的VALUE值BFS类函数名称函数原型功能描述BFSBFSINTGRAPH,INT,INTBFS对象初始化MAZEPATHVOIDMAZEPATHBFS算法寻找生成迷宫路径HASPATHBOOLHASPATHINTX,INTY有可访问迷宫格判断PRINTPATHVOIDPRINTPATHDOS界面打印路径GETVALUEINTGETVALUEINT,INT获得BFS对象某个迷宫格的VALUE值MFC应用程序函数名称函数原型功能描述ONBNCLICKEDCREATEMAZEONBNCLICKEDCREATEMAZE点击“生成迷宫”按钮随机生成迷宫，并且在窗口进行显示ONBNCLICKEDDFSONBNCLICKEDDFS点击“DFS寻路”按钮在生成迷宫上进行DFS寻路，在窗口显示ONBNCLICKEDBFSONBNCLICKEDBFS点击“BFS寻路”按钮在生成迷宫上进行BFS寻路，在窗口显示ONBNCLICKEDEXITONBNCLICKEDEXIT点击“退出按钮”,程序关闭退出ONBNCLICKEDABOUTONBNCLICKEDABOUT点击“关于”按钮，显示程序使用说明及其他2本系统函数的调用关系见图21OMFC程序初始化按钮生成迷宫按钮DFS寻路按钮BFS寻路按钮退出按钮关于使用MAZE类创建一个对象，随机生成迷宫使用DFS类创建一个对象，进行DFS路径寻找使用BFS类创建一个对象，今夏BFS路径寻找进行BFS路径寻找退出并关闭应用程序弹出窗口，显示使用说明等内容MAZE类对象创建构造函数进行初始化，构建节点矩阵和迷宫矩阵CREATEMAZE函数根据节点矩阵进行迷宫的随机创建，并将生成迷宫保存在迷宫矩阵中迷宫随机生成完成算法阐述迷宫节点以及相关功能函数定义规定墙占用格子规定每个节点代表一个可通过格子，节点有四面墙边框为墙采用深度优先算法生成迷宫IF存在可访问节点IF存在当前节点可访问的邻节点随机获得邻节点清空当前结点和邻节点中间的墙当前结点入栈设置邻节点属性为已访问邻节点置为当前结点ELSEIF若栈不为空令栈顶节点为当前结点ELSE随机取节点置为当前结点DFS对象创建DFS对象初始化MAZEPATH进行DFS寻路，并将结果保存在矩阵中DFS寻路完成算法阐述使用GRAPH进行DFS搜索，GRAPH为二维数组，其中1为墙，0为路WHILE存在未访问迷宫格IF存在当前迷宫格可访问的邻格子当前迷宫格周围（上下左右）存在格子为0IF存在向下的格子当前格子入栈向下邻格子设为当前格子访问数ELSE当前格子入栈邻格子设为当前格子访问数ELSEIF若栈不为空令栈顶格子为当前格子ELSE随机取格子置为当前格子BFS对象创建BFS对象初始化MAZEPATH进行BFS寻路，并将结果保存在矩阵中BFS寻路完成算法阐述CURSTARTCUR入队WHILE（队不空）IF到达出口BREAKIF有可访问邻点该邻点入队设置该邻点已访问CURFRONTFRONT出队3详细设计（对概要设计部分所介绍的功能模块进行详细介绍及实现。并给出相应函数的定义即实现函数。）1节点类型和指针类型MAZECELLMATRIX存储迷宫节点的数组STACKMAZESTACK存放节点的堆栈迷宫中节点类型的定义TYPEDEFCLASSMAZECELLPRIVATEBOOLISACCESSED/可访问性INTX,Y/坐标INTWALL4/四面墙BOOLFLAGS/标记一个节点是否已被访问MAZENODE2迷宫的操作（1）创建迷宫VOIDMAZECREATEMAZECURRENTCELL/从0,0开始访问CURRENTCELLISACCESSEDTRUE/初始点为0,0标记为真ACCESSED1/访问节点加1TONEXTNODE/寻找下一节点FORINTI0IXINTCURRENTYCURRENTCOORDINATEYMAZEPOINTERCURRENTXCURRENTYACCESSEDTRUEMAZEPOINTERCURRENTXCURRENTYVALUE2INTIWHILECURRENTXM1CURRENTXCURRENTCOORDINATEXCURRENTYCURRENTCOORDINATEYI1/记录有效相邻格子数COUTACCESSEDTRUEPATHSTACKPUSHCURRENTCOORDINATE/将上一个格子坐标进栈CURRENTCOORDINATETEMPICURRENTCOORDINATEVALUE2CURRENTCOORDINATEACCESSEDTRUEACCESSECOUNTCURRENTXCURRENTCOORDINATEXCURRENTYCURRENTCOORDINATEYELSEIFPATHSTACKEMPTY/当前格子无可走的相邻格子，返回到上一个格子MAZEPOINTERCURRENTXCURRENTYVALUE1CURRENTCOORDINATEPATHSTACKPOP4BFS算法实现VOIDBFSMAZEPATHCURRENTCOORDINATENEWCOORDINATEBFS0,STARTINTCOUNT10,COUNT20/COUNT1为记录前一个被访问格子（栈顶部格子）可走相邻格子数，COUNT2为当前访问格子的可走相邻格子数INTCURRENTXCURRENTCOORDINATEXINTCURRENTYCURRENTCOORDINATEYMAZEPOINTERCURRENTXCURRENTYACCESSEDTRUEMAZEPOINTERCURRENTXCURRENTYVALUE2/INTENTRYSTARTPOINT/入口ID/INTEXITENDPOINT/出口ID/记录所有房间的访问路径,TRAPATHI表示访问到房间I的路径上的前一节点/VECTORTRAPATHENDPOINT,1/DEPATHQUERYPATHQUERYS_I0SNEWCSTRINGMNPATHQUERYPUSH_BACKMAZEPOINTER0STARTWHILEPATHQUERYEMPTYIFCURRENTXM1BREAKINTI0/IFMAZEPOINTERCURRENTXCURRENTYVALUE2/如果已经该房间已经访问过了，则跳过/CONTINUEIFHASPATHCURRENTX,CURRENTY1PATHQUERYPUSH_BACKMAZEPOINTERCURRENTXCURRENTY1/MAZEPOINTERCURRENTXCURRENTY1VALUE2CURRENTCOORDINATEACCESSEDTRUEIIFHASPATHCURRENTX,CURRENTY1PATHQUERYPUSH_BACKMAZEPOINTERCURRENTXCURRENTY1/MAZEPOINTERCURRENTXCURRENTY1VALUE2CURRENTCOORDINATEACCESSEDTRUEIIFHASPATHCURRENTX1,CURRENTYPATHQUERYPUSH_BACKMAZEPOINTERCURRENTX1CURRENTY/MAZEPOINTERCURRENTX1CURRENTYVALUE2CURRENTCOORDINATEACCESSEDTRUEIIFHASPATHCURRENTX1,CURRENTYPATHQUERYPUSH_BACKMAZEPOINTERCURRENTX1CURRENTY/MAZEPOINTERCURRENTX1CURRENTYVALUE2CURRENTCOORDINATEACCESSEDTRUEIIFI0MAZEPOINTERCURRENTXCURRENTYVALUE1ELSEMAZEPOINTERCURRENTXCURRENTYVALUE2PATHQUERYPOP_FRONTCURRENTCOORDINATECURRENTXCURRENTCOORDINATEXCURRENTYCURRENTCOORDINATEYSS_IFORMAT_T“D,DN“,CURRENTX,CURRENTY/COUTLOADICONIDR_MAINFRAMEVOIDCMAZE_MFCDLGDODATAEXCHANGECDATAEXCHANGEPDXCDIALOGEXDODATAEXCHANGEPDXDDX_TEXTPDX,IDC_ROW,M_MAZEXDDX_TEXTPDX,IDC_COLUMN,M_MAZEYDDX_CONTROLPDX,IDC_LIST,M_PATHCOORDINATEBEGIN_MESSAGE_MAPCMAZE_MFCDLG,CDIALOGEXON_WM_SYSCOMMANDON_WM_PAINTON_WM_QUERYDRAGICONON_BN_CLICKEDIDC_CREATEMAZE,/将“关于”菜单项添加到系统菜单中。/IDM_ABOUTBOX必须在系统命令范围内。ASSERTIDM_ABOUTBOXASSERTIDM_ABOUTBOXAPPENDMENUMF_SEPARATORPSYSMENUAPPENDMENUMF_STRING,IDM_ABOUTBOX,STRABOUTMENU/设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动/执行此操作SETICONM_HICON,TRUE/设置大图标SETICONM_HICON,FALSE/设置小图标/TODO在此添加额外的初始化代码RETURNTRUE/除非将焦点设置到控件，否则返回TRUEVOIDCMAZE_MFCDLGONSYSCOMMANDUINTNID,LPARAMLPARAMIFNIDDLGABOUTDOMODALELSECDIALOGEXONSYSCOMMANDNID,LPARAM/如果向对话框添加最小化按钮，则需要下面的代码/来绘制该图标。对于使用文档/视图模型的MFC应用程序，/这将由框架自动完成。VOIDCMAZE_MFCDLGONPAINTIFISICONICCPAINTDCDCTHIS/用于绘制的设备上下文SENDMESSAGEWM_ICONERASEBKGND,REINTERPRET_CASTDCGETSAFEHDC,0/使图标在工作区矩形中居中INTCXICONGETSYSTEMMETRICSSM_CXICONINTCYICONGETSYSTEMMETRICSSM_CYICONCRECTRECTGETCLIENTRECTINTXRECTWIDTHCXICON1/2INTYRECTHEIGHTCYICON1/2/绘制图标DCDRAWICONX,Y,M_HICONELSECDIALOGEXONPAINT/当用户拖动最小化窗口时系统调用此函数取得光标/显示。HCURSORCMAZE_MFCDLGONQUERYDRAGICONRETURNSTATIC_CASTM_HICON32数据录入实现M,N取默认值50，50M,N取默认值20，20M,N取默认值60,604调试分析（该部分内容包括对准备进行测试的数据进行测试，并对在调试过程中遇到的问题是如何分析和解决的进行描述。）1问题1数组越界问题描述寻路过程，发生越界的情况问题解决搜寻路径是添加越界检查函数2问题2死循环问题描述迷宫创建过程，发生死循环情况问题解决添加判断语句判断当前节点是否已到达终点3问题3坐标问题问题描述只能输出一个坐标问题解决使用CSTRING数组存储所有节点的坐标，最后输出5用户使用说明此处说明如何使用你所设计的软件1输入X和Y的值，点击生成迷宫进行随机生成，可重复点击，随机生成。2如未输入X和Y的值，则默认值为50，点击生成迷宫按钮，随机生成迷宫，可重复生成。3生成迷宫之后，点击DFS寻路，会生成DFS路径，寻路坐标表示在右边空栏。4生成迷宫之后，点击BFS寻路，会生成BFS路径，寻路坐标表示在右边空栏。5点击退出按钮，程序会关闭退出6点击相关按钮，会提示应用程序使用说明。6测试结果（此处应对你所设计的软件和经过测试，下个结论。分别使用默认值50，50输入值（20，20）（60，60）进行迷宫生成，DFS寻路，BFS寻路测试，测试结果如下结论通过本次课程设计可以得出结论如下1迷宫深度优先算法可以迅速生成一个矩形迷宫，但是生成迷宫具有一条明显的通路。2迷宫DFS路径探索，可以明显在使用较少计算量的情况下的寻求一条迷宫通路。3迷宫BFS路径探索，需要进行大量的计算，其速度不如DFS路径探索但可以找到具有最优解的路径。4通过本次课程设计，深入探索了栈，队列等数据结构的应用，以及深刻学习了DFS算法和BFS算法在实际中的应用，并且对于程序编写能力进行了显著锻炼。致谢本次课程设计能够得到这样的成果，感谢指导老师的倾力执导，以及各位组员的辛勤努力。7附录程序源代码BFSHPRAGMAONCEINCLUDEINCLUDE“MAZEH“INCLUDEUSINGNAMESPACESTDCLASSCOORDINATEBFSFRIENDCLASSBFSPUBLICCOORDINATEBFSXYVALUE0ACCESSEDFALSECOORDINATEBFSINTA,INTBXAYBVALUE0ACCESSEDFALSEINTGETXINTGETYINTXINTYINTVALUEBOOLACCESSEDCLASSBFS/TODOPUBLICCSTRINGSINTS_IBFSINTGRAPH,INTGRAPHROW,INTGRAPHCOLUMNBFS/VOIDGETMAZEINT,INT,INTVOIDMAZEPATHBOOLHASPATHINTX,INTYVOIDPRINTPATHINTGETVALUEINT,INTPRIVATECOORDINATEBFSMAZEPOINTERINTMINTNINTSTARTINTENDDEQUEPATHQUERYINTACCESSECOUNTCOORDINATEBFSCURRENTCOORDINATEBFSCPPINCLUDE“STDAFXH“INCLUDE“BFSH“INTCOORDINATEBFSGETXRETURNXINTCOORDINATEBFSGETYRETURNYBFSBFSINTGRAPH,INTGRAPHROW,INTGRAPHCOLUMNMGRAPHROWNGRAPHCOLUMNACCESSECOUNT1MAZEPOINTERNEWCOORDINATEBFSGRAPHROWFORINTI0IM1RETURNFALSEIFYN1RETURNFALSE/访问检测IFMAZEPOINTERXYACCESSEDRETURNFALSEIFMAZEPOINTERXYVALUE0RETURNFALSERETURNTRUE/CURSTART/CUR入队/WHILE（队不空）/IF到达出口/BREAK/如果CUR已访问/CONTINUE/IF有可访问邻点/该邻点入队/设置该邻点已访问/CURFRONT/FRONT出队VOIDBFSMAZEPATHCURRENTCOORDINATENEWCOORDINATEBFS0,STARTINTCOUNT10,COUNT20/COUNT1为记录前一个被访问格子（栈顶部格子）可走相邻格子数，COUNT2为当前访问格子的可走相邻格子数INTCURRENTXCURRENTCOORDINATEXINTCURRENTYCURRENTCOORDINATEYMAZEPOINTERCURRENTXCURRENTYACCESSEDTRUEMAZEPOINTERCURRENTXCURRENTYVALUE2/INTENTRYSTARTPOINT/入口ID/INTEXITENDPOINT/出口ID/记录所有房间的访问路径,TRAPATHI表示访问到房间I的路径上的前一节点/VECTORTRAPATHENDPOINT,1/DEPATHQUERYPATHQUERYS_I0SNEWCSTRINGMNPATHQUERYPUSH_BACKMAZEPOINTER0STARTWHILEPATHQUERYEMPTYIFCURRENTXM1BREAKINTI0/IFMAZEPOINTERCURRENTXCURRENTYVALUE2/如果已经该房间已经访问过了，则跳过/CONTINUEIFHASPATHCURRENTX,CURRENTY1PATHQUERYPUSH_BACKMAZEPOINTERCURRENTXCURRENTY1/MAZEPOINTERCURRENTXCURRENTY1VALUE2CURRENTCOORDINATEACCESSEDTRUEIIFHASPATHCURRENTX,CURRENTY1PATHQUERYPUSH_BACKMAZEPOINTERCURRENTXCURRENTY1/MAZEPOINTERCURRENTXCURRENTY1VALUE2CURRENTCOORDINATEACCESSEDTRUEIIFHASPATHCURRENTX1,CURRENTYPATHQUERYPUSH_BACKMAZEPOINTERCURRENTX1CURRENTY/MAZEPOINTERCURRENTX1CURRENTYVALUE2CURRENTCOORDINATEACCESSEDTRUEIIFHASPATHCURRENTX1,CURRENTYPATHQUERYPUSH_BACKMAZEPOINTERCURRENTX1CURRENTY/MAZEPOINTERCURRENTX1CURRENTYVALUE2CURRENTCOORDINATEACCESSEDTRUEIIFI0MAZEPOINTERCURRENTXCURRENTYVALUE1ELSEMAZEPOINTERCURRENTXCURRENTYVALUE2PATHQUERYPOP_FRONTCURRENTCOORDINATECURRENTXCURRENTCOORDINATEXCURRENTYCURRENTCOORDINATEYSS_IFORMAT_T“D,DN“,CURRENTX,CURRENTY/COUTINCLUDEUSINGNAMESPACESTDCLASSCOORDINATEFRIENDCLASSDFSPUBLICCOORDINATEXYVALUE0ACCESSEDFALSE/HASWAY0HASWAY1HASWAY20/下，左，右COORDINATEINTA,INTBXAYBVALUE0ACCESSEDFALSE/HASWAY0HASWAY1HASWAY20INTGETXINTGETYINTXINTYINTVALUEBOOLACCESSED/INTHASWAY3CLASSDFS/TODOPUBLICCSTRINGSINTS_IDFSINTGRAPH,INTGRAPHROW,INTGRAPHCOLUMNDFS/VOIDGETMAZEINT,INT,INTVOIDMAZEPATHBOOLHASPATHINTX,INTYVOIDPRINTPATHINTGETVALUEINT,INTPRIVATECOORDINATEMAZEPOINTERINTMINTNINTSTARTINTENDSTACKPATHSTACKINTACCESSECOUNTCOORDINATECURRENTCOORDINATEDFSCPPINCLUDE“STDAFXH“INCLUDE“DFSH“INTCOORDINATEGETXRETURNXINTCOORDINATEGETYRETURNYDFSDFSINTGRAPH,INTGRAPHROW,INTGRAPHCOLUMNMGRAPHROWNGRAPHCOLUMNACCESSECOUNT1MAZEPOINTERNEWCOORDINATEGRAPHROWFORINTI0IM1RETURNFALSEIFYN1RETURNFALSE/访问检测IFMAZEPOINTERXYACCESSEDRETURNFALSEIFMAZEPOINTERXYVALUE0RETURNFALSERETURNTRUEVOIDDFSMAZEPATHCURRENTCOORDINATENEWCOORDINATE0,STARTINTCOUNT10,COUNT20/COUNT1为记录前一个被访问格子（栈顶部格子）可走相邻格子数，COUNT2为当前访问格子的可走相邻格子数INTCURRENTXCURRENTCOORDINATEXINTCURRENTYCURRENTCOORDINATEYMAZEPOINTERCURRENTXCURRENTYACCESSEDTRUEMAZEPOINTERCURRENTXCURRENTYVALUE2INTIS_I0SNEWCSTRINGMNWHILECURRENTXM1/当还有格子没被访问时CURRENTXCURRENTCOORDINATEXCURRENTYCURRENTCOORDINATEYI1/记录有效相邻格子数/COUTACCESSEDTRUEPATHSTACKPUSHCURRENTCOORDINATE/将上一个格子坐标进栈CURRENTCOORDINATETEMPICURRENTCOORDINATEVALUE2CURRENTCOORDINATEACCESSEDTRUEACCESSECOUNTCURRENTXCURRENTCOORDINATEXCURRENTYCURRENTCOORDINATEYELSEIFPATHSTACKEMPTY/当前格子无可走的相邻格子，返回到上一个格子MAZEPOINTERCURRENTXCURRENTYVALUE1CURRENTCOORDINATEPATHSTACKPOPVOIDDFSPRINTPATHFORINTI0IINCLUDEINCLUDEINCLUDEINCLUDE“MAZECELLH“USINGNAMESPACESTDCLASSMAZEFRIENDVOIDDRAWMAZEVOIDPUBLICMAZEINTM49,INTN49VOIDCREATEMAZE/迷宫生成器VOIDPRINTMAZE/打印迷宫BOOLHASUNACCESSADJNODEINT,INT/判断当前节点的某临节点是否能成为下个当前节点VOIDBREAKWALLMAZECELL/拆掉两个节点之间墙的函数VOIDTONEXTNODEVOIDMAKERANDOMSTARTANDENDINTGETGRAPHROWINTGETGRAPHCOLUMNINTGETGRAPHMAZE/清除动态申请内存VOIDBFSPRIVATEINTSTARTPOINT/迷宫入口坐标INTENDPOINT/迷宫出口坐标INTROW/节点矩阵行INTCOLUMN/节点矩阵列数STACKMAZESTACK/存放节点的堆栈MAZECELLMATRIX/生成迷宫的节点矩阵INTTOTAL/节点的总个数INTACCESSED/被访问过的节点个数INTGRAPH/迷宫图INTGRAPHROW/迷宫的行数INTGRAPHCOLUMN/迷宫的列数MAZECELLCURRENTCELL/正在访问的节点MAZECPPINCLUDE“STDAFXH“INCLUDE“MAZEH“MAZEMAZEINTM,INTNWHILEM20|N20/强行定义MN为奇数IFM20MELSENACCESSED0/访问过的节点数初始化为0/生成的迷宫与所构造的节点矩阵不同，ROWCOLUMN为节点矩阵的行，列ROWM1/2COLUMNN1/2TOTALROWCOLUMN/所有的节点数SRANDUNSIGNEDINTTIME0/初始化节点矩阵MATRIXNEWMAZECELLROWFORINTI0IXCURRENTCELLX/关系为上下相邻RELATIONTEMPCELLXCURRENTCELLXIFRELATION1CURRENTCELLWALL1TEMPCELLWALL00ELSECURRENTCELLWALL0TEMPCELLWALL10ELSE/左右相邻RELATIONTEMPCELLYCURRENTCELLYIFRELATION1CURRENTCELLWALL3TEMPCELLWALL20ELSECURRENTCELLWALL2TEMPCELLWALL30BOOLMAZEHASUNACCESSADJNODEINTX,INTY/判断当前节点的某个相临节点是否能成为下个当前节点/越界检测IFXROW1RETURNFALSEIFYCOLUMN1RETURNFALSE/访问检测IFMATRIXXYISACCESSEDRETURNFALSERETURNTRUEVOIDMAZETONEXTNODEINTCOUNT10,COUNT20/COUNT1为记录前一个被访问节点（堆栈顶部节点）有效相邻节点数，COUNT2为当前访问节点的有效相邻节点数INTCURRENTXCURRENTCELLXINTCURRENTYCURRENTCELLYMAZECELLADJCELL/存放选好的下一个要访问的节点WHILETOTALACCESSED/当还有点没被访问时INTI0/记录有效相邻节点数MAZECELLTEMP4/存放有效相邻节点的数组IFHASUNACCESSADJNODECURRENTX1,CURRENTYTEMPIIIFHASUNACCESSADJNODECURRENTX1,CURRENTYTEMPIIIFHASUNACCESSADJNODECURRENTX,CURRENTY1TEMPIIIFHASUNACCESSADJNODECURRENTX,CURRENTY1TEMPIIIFACCESSED0COUNT2IELSEINTTTCOUNT2COUNT2ICOUNT1TIFI0INTSRANDIADJCELLTEMPSBREAKWALLADJCELL/拆墙MAZESTACKPUSHCURRENTCELL/将上一个节点进栈CURRENTCELLADJCELLCURRENTCELLISACCESSEDTRUEACCESSEDCURRENTXCURRENTCELLXCURRENTYCURRENTCELLYELSEIFMAZESTACKEMPTYACCESSEDCURRENTCELLMAZESTACKPOPELSE/如若上一个被访问节点只有当前节点一个有效相邻节点，则从所有被访问过的节点中随机选取一个作为当前节点（从路径展开分支，保证路径不会断）MAZESTACKPUSHCURRENTCELLINTA1RANDROW,A2RANDCOLUMNWHILEMATRIXA1A2ISACCESSEDA1RANDROWA2RANDCOLUMNCURRENTCELLCURRENTXCURRENTCELLXCURRENTYCURRENTCELLY/以下根据节点矩阵生成迷宫VOIDMAZEMAKERANDOMSTARTANDENDSTARTPOINT2RANDROW1ENDPOINT2RANDROW1GRAPH0STARTPOINTGRAPHGRAPHROW1ENDPOINT0INTMAZEGETGRAPHROWRETURNGRAPHROWINTMAZEGETGRAPHCOLUMNRETURNGRAPHCOLUMNINTMAZEGETGRAPHRETURNGRAPHVOIDMAZECREATEMAZECURRENTCELL/从0,0开始访问，也可以随机取一个节点CURRENTCELLISACCESSEDTRUE/初始点为0,0,并标记ACCESSED1TONEXTNODEFORINTI0ILOADICONIDR_MAINFRAMEVOIDCMAZE_MFCDLGDODATAEXCHANGECDATAEXCHANGEPDXCDIALOGEXDODATAEXCHANGEPDXDDX_TEXTPDX,IDC_ROW,M_MAZEXDDX_TEXTPDX,IDC_COLUMN,M_MAZEYDDX_CONTROLPDX,IDC_LIST,M_PATHCOORDINATEBEGIN_MESSAGE_MAPCMAZE_MFCDLG,CDIALOGEXON_WM_SYSCOMMANDON_WM_PAINTON_WM_QUERYDRAGICONON_BN_CLICKEDIDC_CREATEMAZE,/将“关于”菜单项添加到系统菜单中。/IDM_ABOUTBOX必须在系统命令范围内。ASSERTIDM_ABOUTBOXASSERTIDM_ABOUTBOXAPPENDMENUMF_SEPARATORPSYSMENUAPPENDMENUMF_STRING,IDM_ABOUTBOX,STRABOUTMENU/设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动/执行此操作SETICONM_HICON,TRUE/设置大图标SETICONM_HICON,FALSE/设置小图标/TODO在此添加额外的初始化代码RETURNTRUE/除非将焦点设置到控件，否则返回TRUEVOIDCMAZE_MFCDLGONSYSCOMMANDUINTNID,LPARAMLPARAMIFNIDDLGABOUTDOMODALELSECDIALOGEXONSYSCOMMANDNID,LPARAM/如果向对话框添加最小化按钮，则需要下面的代码/来绘制该图标。对于使用文档/视图模型的MFC应用程序，/这将由框架自动完成。VOIDCMAZE_MFCDLGONPAINTIFISICONICCPAINTDCDCTHIS/用于绘制的设备上下文SENDMESSAGEWM_ICONERASEBKGND,REINTERPRET_CASTDCGETSAFEHDC,0/使图标在工作区矩形中居中INTCXICONGETSYSTEMMETRICSSM_CXICONINTCYICONGETSYSTEMMETRICSSM_CYICONCRECTRECTGETCLIENTRECTINTXRECTWIDTHCXICON1/2INTYRECTHEIGHTCYICON1/2/绘制图标DCDRAWICONX,Y,M_HICONELSECDIALOGEXONPAINT/当用户拖动最小化窗口时系统调用此函数取得光标/显示。HCURSORCMAZE_MFCDLGONQUERYDRAGICONRETURNSTATIC_CASTM_HICONINTRINTCINTARRVOIDCMAZE_MFCDLGONBNCLICKEDCREATEMAZE/TODO在此添加控件通知处理程序代码INTM,NUPDATEDATATRUEIFM_MAZEX0|M_MAZEY0M50N50ELSEMINTM_MAZEXNINTM_MAZEYMAZEMAZEM,N/创建迷宫对象MAZECREATEMAZERMAZEGETGRAPHROWCMAZEGETGRAPHCOLUMNARRMAZEGETGRAPHARRNEWINTMAZEGETGRAPHROWFORINTI0IMAZEGETGRAPHROWIARRINEWINTMAZEGETGRAPHCOLUMNFORINTI0IRIFORINTJ0JCJARRIJMAZEGETGRAPHIJ/DOUBLELENGTH50/DOUBLEWIDE50/INTX5INTY5/HDCHDCGETDCM_HWNDHBRUSHHBRUSH_BK,HBRUSHOLD_BKHBRUSH_BKCREATESOLIDBRUSHRGB255,255,255HBRUSHOLD_BKHBRUSHSELECTOBJECTHDC,HBRUSH_BKRECTANGLEHDC,0,0,700,700SELECTOBJECTHDC,HBRUSHOLD_BKDELETEOBJECTHBRUSH_BKFORINTI0IRIFORINTJ0JCJIFARRIJ1/墙HBRUSHHBRUSH,HBRUSHOLDHBRUSHCREATESOLIDBRUSHRGB138,54,15HBRUSHOLDHBRUSHSELECTOBJECTHDC,HBRUSHRECTANGLEHDC,I10,J10,I1010,J1010SELECTOBJECTHDC,HBRUSHOLDDELETEOBJECTHBRUSHRELEASEDCM_HWND,HDCVOIDCMAZE_MFCDLGONBNCLICKEDDFS/TODO在此添加控件通知处理程序代码DFSDFSARR,R,CDFSMAZEPATH/DFSPRINTPATH/HDCHDCGETDCM_HWNDFORINTI0IRIFORINTJ0JCJIFDFSGETVALUEI,J2HBRUSHHBRUSH,HBRUSHOLDHBRUSHCREATESOLIDBRUSHRGB0,0,255HBRUSHOLDHBRUSHSELECTOBJECTHDC,HBRUSHRECTANGLEHDC,I10,J10,I1010,J1010SELECTOBJECTHDC,HBRUSHOLDDELETEOBJECTHBRUSHELSEIFDFSGETVALUEI,J1HBRUSHHBRUSH_2,HBRUSHOLD_2HBRUSH_