(最新整理)迷宮問題的C,C++算法實(shí)現(xiàn)

1、(完整)迷宮問題的c,c+算法實(shí)現(xiàn)(完整)迷宮問題的c,c+算法實(shí)現(xiàn) 編輯整理：尊敬的讀者朋友們：這里是精品文檔編輯中心，本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的，發(fā)布之前我們對(duì)文中內(nèi)容進(jìn)行仔細(xì)校對(duì)，但是難免會(huì)有疏漏的地方，但是任然希望（(完整)迷宮問題的c,c+算法實(shí)現(xiàn)）的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來便利。同時(shí)也真誠(chéng)的希望收到您的建議和反饋，這將是我們進(jìn)步的源泉，前進(jìn)的動(dòng)力。本文可編輯可修改，如果覺得對(duì)您有幫助請(qǐng)收藏以便隨時(shí)查閱，最后祝您生活愉快 業(yè)績(jī)進(jìn)步，以下為(完整)迷宮問題的c,c+算法實(shí)現(xiàn)的全部?jī)?nèi)容。基于棧的c語(yǔ)言迷宮問題與實(shí)現(xiàn)一 問題描述多年以來,迷宮問題一直是令人感興趣的題

2、目。實(shí)驗(yàn)心理學(xué)家訓(xùn)練老鼠在迷宮中尋找食物。許多神秘主義小說家也曾經(jīng)把英國(guó)鄉(xiāng)村花園迷宮作為謀殺現(xiàn)場(chǎng)。于是,老鼠過迷宮問題就此產(chǎn)生，這是一個(gè)很有趣的計(jì)算機(jī)問題，主要利用 “?！笔抢鲜笸ㄟ^嘗試的辦法從入口穿過迷宮走到出口。迷宮只有兩個(gè)門，一個(gè)叫做入口,另一個(gè)叫做出口。把一只老鼠從一個(gè)無頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解迷宮問題,即找出從入口到出口的路徑。一個(gè)迷宮可用上圖所示方陣m,n表示，0表示能通過，1 表示不能通過?，F(xiàn)假設(shè)耗子從左上角1,1進(jìn)入迷宮，編寫算法,尋求一條從右下角m,n

3、 出去的路徑.下圖是一個(gè)迷宮的示意圖:二 算法基本思想迷宮求解問題是棧的一個(gè)典型應(yīng)用?；舅惴ㄋ枷胧牵涸谀硞€(gè)點(diǎn)上，按照一定的順序（在本程序中順序?yàn)樯?、右、下、左）?duì)周圍的墻、路進(jìn)行判斷(在本程序中分別用1、0)代替，若周圍某個(gè)位置為0,則移動(dòng)到該點(diǎn)上，再進(jìn)行下一次判斷；若周圍的位置都為1（即沒有通路），則一步步原路返回并判斷有無其他通路，然后再次進(jìn)行相同的判斷，直到走到終點(diǎn)為止，或者確認(rèn)沒有任何通路后終止程序。要實(shí)現(xiàn)上述算法，需要用到棧的思想。棧里面壓的是走過的路徑,若遇到死路,則將該位置（在棧的頂層)彈出，再進(jìn)行下一次判斷；若遇到通路，則將該位置壓棧并進(jìn)行下一次判斷。如此反復(fù)循環(huán)，直到程序結(jié)

4、束。此時(shí)，若迷宮有通路,則棧中存儲(chǔ)的是迷宮通路坐標(biāo)的倒序排列，再把所有坐標(biāo)順序打印后,即可得到正確的迷宮通路。三 程序具體部分的說明1. 迷宮的生成根據(jù)題目的要求，迷宮的大小是自定義輸入的.所以在程序中用malloc申請(qǐng)動(dòng)態(tài)二維數(shù)組。數(shù)組中的元素為隨機(jī)生成的0、1。數(shù)組周圍一圈的元素全部定義為1,以表示邊界。2. 棧的c語(yǔ)言實(shí)現(xiàn)為了實(shí)現(xiàn)棧的功能，即清空、壓棧、彈出、返回棧頂元素，在程序中編寫了相應(yīng)的函數(shù)。makenull 清空棧push 將橫、縱坐標(biāo)壓棧topx 返回棧頂存儲(chǔ)的橫坐標(biāo)topy 返回棧頂存儲(chǔ)的縱坐標(biāo)pop 彈出棧頂元素3. 具體的判斷算法當(dāng)位置坐標(biāo)（程序中為x y)移到某一位置時(shí)

5、，將這個(gè)位置的值賦值為1并壓棧，以說明該點(diǎn)已經(jīng)走過。接著依次判斷該點(diǎn)的上、右、下、左是否為0，若有一方為0，則移動(dòng)到該位置上，進(jìn)行下次判斷;若為周圍位置全部是1，則將該點(diǎn)壓棧后不斷彈出，每次彈出時(shí)判斷棧頂元素(即走過的路)周圍有無其他通路。如果有的話，則選擇該方向繼續(xù)走下去;如果棧已經(jīng)為空仍然沒有找到出路，則迷宮沒有出口程序結(jié)束。當(dāng)x y走到出口坐標(biāo)時(shí)，程序判斷部分結(jié)束。棧里面存儲(chǔ)的是每個(gè)走過的點(diǎn)的坐標(biāo),將這些橫縱坐標(biāo)分別存儲(chǔ)在兩個(gè)數(shù)組中，最后將數(shù)組中的坐標(biāo)元素倒序輸出，即得到了完整的路徑.四 程序源代碼及注釋 / maze.cpp ： 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)./include stdaf

6、x.h”includestdio。h#includestring.h#include #includetime.htypedef int elementtype；struct nodeelementtype val1;elementtype val2； node *next;/定義結(jié)構(gòu)體typedef node maze；void makenull(maze &s）;void push(elementtype x,elementtype y, maze s）；void pop（maze s);elementtype topx(maze s)；elementtype topy（maze s);/

7、申明函數(shù)int _tmain（int argc, _tchar argv)int p,q，x1，y1，i，j,k，n1，n2,m1，m2，l,w,max;int x,y;int a,b,c,d； printf(”輸入迷宮長(zhǎng)度及寬度l和wn”)； scanf(”d %d，l，&w);getchar();n1=w+2;n2=l+2;/為迷宮加上邊界max=n1*n2; p=(int)malloc（n1sizeof（int)）; for(i=0；in1；i+） pi=(int *)malloc(n2*sizeof（int)；/生成二維動(dòng)態(tài)數(shù)組 srand(time(null)；x1=（int*)ma

8、lloc(maxsizeof（int）;/生成動(dòng)態(tài)數(shù)組用于存儲(chǔ)路徑y(tǒng)1=（int ）malloc（maxsizeof（int）)；/生成動(dòng)態(tài)數(shù)組用于存儲(chǔ)路徑 for(i=0;imax；i+) x1i=0;for（i=0;imax；i+） y1i=0；/先將存儲(chǔ)路徑的數(shù)組元素全賦值為0 for(i=0；in1;i+) for(j=0；jn2；j+） if(i=0 | j=0） pij=1； else if（i=n1-1 | j=n2-1） pij=1; else pij=rand()2+0; /生成二維1 0隨機(jī)數(shù)組p11=0;pn1-2n2-2=0;/定義迷宮的入口及出口 printf（生成的

9、迷宮如下(代表墻0代表路）：n)； for（i=0；i=0;) if（x1i!=0 & （x1i!=x1i1 | y1i！=y1i1) printf（%d ，d ，x1i，y1i)； i-; else if（x1i!=0 & （x1i=x1i1 & y1i=y1i1）) printf（ ”，x1i，y1i); i=i-2； else i;/倒序打印數(shù)組得到順序出路坐標(biāo)printf(,n1-2，n2-2);/打印出口坐標(biāo) getchar();return 0；void makenull（maze s) /清空棧的函數(shù)s = new node；s-next = null；void push(ele

10、menttype x，elementtype y， maze s）/壓棧函數(shù)maze stk;stk = new node；stkval1 = x;stkval2 = y；stknext = snext;s-next = stk；void pop(maze s）/彈出函數(shù)maze stk；if(snext)stk = snext；snext = stknext；delete stk；elementtype topx(maze s）/返回橫坐標(biāo)函數(shù)if（s-next)return(s-next-val1)；elsereturn null；elementtype topy（maze s)/返回縱坐

11、標(biāo)函數(shù)if(s-next）return(s-nextval2）;elsereturn null；另一種方法實(shí)現(xiàn)的迷宮代碼#ifndef mmigong_hdefine mmigong_h#define max_size 100includeusing namespace std；struct nodeint x；int y;int di；;class stackprivate:int rrow;int ccolm;int top;int count;int minlenght；node stackmax_size;node sstackmax_size；public：stack（)； /初始化

12、/int insortmigong(); /輸入迷宮（即一個(gè)二維數(shù)組)void findpath（int ab10); /找出迷宮的出路；stack:：stack（) /初始化rrow=0；ccolm=0;top=-1；count=1;minlenght=max_size；/*int * stack:：insortmigong(） /輸入迷宮(即一個(gè)二維數(shù)組）int row=1,colm=1;while(true)cout”請(qǐng)輸入迷宮的行數(shù)和列數(shù)：;cinrowcolm;if（row=0|colm=0）cout”輸入錯(cuò)誤!請(qǐng)重新輸入:endl;rrow=row；ccolm=colm；conti

13、nue；elserrow=row；ccolm=colm；break;int mg；coutmgij;return mg；*/void stack:findpath（int ab10) /找出迷宮的出路int a,b，di,find，k;top+;stacktop。x=1;stacktop。y=1;stacktop.di=-1；ab11=-1；while（top1)a=stacktop。x；b=stacktop。y;di=stacktop。di;if（a=8&b=8)coutcount+”:”endl;for（int k=0；k=top；k+）cout”(stackk.x”，stackk。y”)

14、;if(?。?k+1）%15）)coutendl；coutendl;if（top+1minlenght）for(k=0；k=top；k+)sstackk=stackk;minlenght=top+1;abstacktop.xstacktop.y=0；top-；a=stacktop。x;b=stacktop。y；di=stacktop。di；find=0;while（di8！find)di+;switch（di)case 0:a=stacktop.x-1;b=stacktop.y；break；case 1：a=stacktop.x;b=stacktop.y+1;break；case 2：a=st

15、acktop.x+1;b=stacktop.y;break；case 3：a=stacktop。x；b=stacktop.y-1;break； if(abab=0)find=1;if （find=1） stacktop。di=di;top+；stacktop。x=a;stacktop.y=b；stacktop.di=-1;abab=1；elseabstacktop.xstacktop.y=0；top-;coutendl；cout”走出迷宮最短的路徑是：endl；cout其長(zhǎng)度為:minlenghtendl；cout”路徑是:endl；for(k=0；kminlenght;k+）cout（sstackk.x”,sstackk。x”）”；if(kminlenght-1）cout”-；if(!(（k+1）%10)coutendl；coutendl；#endif#includemmigong.hvoid main(）stack stack;int ab1010=1,1