迷宮問題的C,C++算法實現(xiàn)

1、基于棧的C語言迷宮問題與實現(xiàn)一 問題描述多年以來，迷宮問題一直是令人感興趣的題目。實驗心理學(xué)家訓(xùn)練老鼠在迷宮中尋找食物。許多神秘主義小說家也曾經(jīng)把英國鄉(xiāng)村花園迷宮作為謀殺現(xiàn)場。于是，老鼠過迷宮問題就此產(chǎn)生，這是一個很有趣的計算機問題，主要利用 “棧”是老鼠通過嘗試的辦法從入口穿過迷宮走到出口。迷宮只有兩個門，一個叫做入口，另一個叫做出口。把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。求解迷宮問題，即找出從入口到出口的路徑。一個迷宮可用上圖所示方陣m,n表示，0表示能通過，1 表

2、示不能通過?，F(xiàn)假設(shè)耗子從左上角1,1進入迷宮，編寫算法，尋求一條從右下角m,n 出去的路徑。下圖是一個迷宮的示意圖：二 算法基本思想迷宮求解問題是棧的一個典型應(yīng)用。基本算法思想是：在某個點上，按照一定的順序（在本程序中順序為上、右、下、左）對周圍的墻、路進行判斷（在本程序中分別用1、0）代替，若周圍某個位置為0，則移動到該點上，再進行下一次判斷；若周圍的位置都為1（即沒有通路），則一步步原路返回并判斷有無其他通路，然后再次進行相同的判斷，直到走到終點為止，或者確認沒有任何通路后終止程序。要實現(xiàn)上述算法，需要用到棧的思想。棧里面壓的是走過的路徑，若遇到死路，則將該位置（在棧的頂層）彈出，再進行下

3、一次判斷；若遇到通路，則將該位置壓棧并進行下一次判斷。如此反復(fù)循環(huán)，直到程序結(jié)束。此時，若迷宮有通路，則棧中存儲的是迷宮通路坐標的倒序排列，再把所有坐標順序打印后，即可得到正確的迷宮通路。三 程序具體部分的說明1. 迷宮的生成根據(jù)題目的要求，迷宮的大小是自定義輸入的。所以在程序中用malloc申請動態(tài)二維數(shù)組。數(shù)組中的元素為隨機生成的0、1。數(shù)組周圍一圈的元素全部定義為1，以表示邊界。2. 棧的C語言實現(xiàn)為了實現(xiàn)棧的功能，即清空、壓棧、彈出、返回棧頂元素，在程序中編寫了相應(yīng)的函數(shù)。MakeNULL 清空棧Push 將橫、縱坐標壓棧Topx 返回棧頂存儲的橫坐標Topy 返回棧頂存儲的縱坐標Po

4、p 彈出棧頂元素3. 具體的判斷算法當位置坐標（程序中為X Y）移到某一位置時，將這個位置的值賦值為1并壓棧，以說明該點已經(jīng)走過。接著依次判斷該點的上、右、下、左是否為0，若有一方為0，則移動到該位置上，進行下次判斷；若為周圍位置全部是1，則將該點壓棧后不斷彈出，每次彈出時判斷棧頂元素（即走過的路）周圍有無其他通路。如果有的話，則選擇該方向繼續(xù)走下去；如果棧已經(jīng)為空仍然沒有找到出路，則迷宮沒有出口程序結(jié)束。當X Y走到出口坐標時，程序判斷部分結(jié)束。棧里面存儲的是每個走過的點的坐標，將這些橫縱坐標分別存儲在兩個數(shù)組中，最后將數(shù)組中的坐標元素倒序輸出，即得到了完整的路徑。四 程序源代碼及注釋 /

5、Maze.cpp : 定義控制臺應(yīng)用程序的入口點。/#include "stdafx.h"#include<stdio.h>#include<string.h>#include<malloc.h>#include <stdlib.h> #include<time.h>typedef int Elementtype;struct nodeElementtype val1;Elementtype val2; node *next;/定義結(jié)構(gòu)體typedef node *MAZE;void MakeNull(MAZE &

6、amp;S);void Push(Elementtype x,Elementtype y, MAZE S);void Pop(MAZE S);Elementtype Topx(MAZE S);Elementtype Topy(MAZE S);/申明函數(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("輸入迷宮長度及寬度l和wn"); scanf("%d %d",&l,&w);g

7、etchar();n1=w+2;n2=l+2;/為迷宮加上邊界max=n1*n2; p=(int*)malloc(n1*sizeof(int); for(i=0;i<n1;i+) pi=(int *)malloc(n2*sizeof(int);/生成二維動態(tài)數(shù)組 srand(time(NULL);x1=(int*)malloc(max*sizeof(int);/生成動態(tài)數(shù)組用于存儲路徑y(tǒng)1=(int *)malloc(max*sizeof(int);/生成動態(tài)數(shù)組用于存儲路徑 for(i=0;i<max;i+) x1i=0;for(i=0;i<max;i+) y1i=0;/先

8、將存儲路徑的數(shù)組元素全賦值為0 for(i=0;i<n1;i+) for(j=0;j<n2;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隨機數(shù)組p11=0;pn1-2n2-2=0;/定義迷宮的入口及出口 printf("生成的迷宮如下（代表墻0代表路）：n"); for(i=0;i<n1;i+) for(j=0;j<n2;j+) printf("%2d",pij); printf("n"

9、;);/打印迷宮 MAZE S; MakeNull(S);/清空棧 i=1;j=1;if(p12=1 && p21=1) printf("There is no way out");a getchar(); return 0;/判斷入口是否就是死路else do if(pi-1j=0) x=i; y=j; Push(x,y,S); pij=1; i=i-1; /判斷能否向上走 else if(pi-1j=1 && pij+1=0) x=i; y=j; Push(x,y,S); pij=1; j=j+1; /判斷能否向右走 else if(pi

10、-1j=1 && pij+1=1 && pi+1j=0) x=i; y=j; Push(x,y,S); k=Topx(S); pij=1; i=i+1; /判斷能否向下走 else if(pi-1j=1 && pij+1=1 && pi+1j=1 && pij-1=0) x=i; y=j; Push(x,y,S); pij=1; j=j-1; /判斷能否向左走 else if(pi-1j=1 && pij+1=1 && pi+1j=1 && pij-1=1)/判斷如果

11、為死路 pij=1; x=i; y=j; Push(x,y,S); for(;) Pop(S);/彈出棧頂元素 x=Topx(S); y=Topy(S);/返回棧頂元素橫縱坐標 if( px-1y=0) i=x-1; j=y; pij=1; x=i; y=j; Push(x,y,S); break; else if(px-1y=1 && pxy+1=0) i=x; j=y+1; pij=1; x=i; y=j; Push(x,y,S); break; else if(px-1y=1 && pxy+1=1 && px+1y=0) i=x+1; j=

12、y; pij=1; x=i; y=j; Push(x,y,S); break; else if(px-1y=1 && pxy+1=1 && px+1y=1 && pxy-1=0) i=x; j=y-1; pij=1; x=i; y=j; Push(x,y,S); break; /判斷彈出后棧頂元素周圍有無通路 else if(x=1 && y=1) printf("There is no way out"); getchar(); return 0; /如果棧頂元素為入口則迷宮無出路 while(i!=n1-2

13、 | j!=n2-2);/循環(huán)截止條件printf("Success!n The route is:n");for(i=0;i+) a=Topx(S); b=Topy(S); Pop(S); x1i=a; y1i=b;/將棧頂元素坐標存儲在數(shù)組中 if(a=1 && b=1) getchar(); break; for(i=max-1;i>=0;) if(x1i!=0 && (x1i!=x1i-1 | y1i!=y1i-1) printf("<%d ,%d> ",x1i,y1i); i-; else if

14、(x1i!=0 && (x1i=x1i-1 && y1i=y1i-1) printf("<%d ,%d> ",x1i,y1i); i=i-2; else i-;/倒序打印數(shù)組得到順序出路坐標printf("<%d ,%d>",n1-2,n2-2);/打印出口坐標 getchar();return 0;void MakeNull(MAZE &S) /清空棧的函數(shù)S = new node;S->next = NULL;void Push(Elementtype x,Elementtype

15、y, MAZE S)/壓棧函數(shù)MAZE stk;stk = new node;stk->val1 = x;stk->val2 = y;stk->next = S->next;S->next = stk;void Pop(MAZE S)/彈出函數(shù)MAZE stk;if(S->next)stk = S->next;S->next = stk->next;delete stk;Elementtype Topx(MAZE S)/返回橫坐標函數(shù)if(S->next)return(S->next->val1);elsereturn N

16、ULL;Elementtype Topy(MAZE S)/返回縱坐標函數(shù)if(S->next)return(S->next->val2);elsereturn NULL;另一種方法實現(xiàn)的迷宮代碼#ifndef MMIGONG_H#define MMIGONG_H#define MAX_SIZE 100#include<iostream>using namespace std;struct Nodeint x;int y;int di;class Stackprivate:int rrow;int ccolm;int top;int count;int minlen

17、ght;Node stackMAX_SIZE;Node sstackMAX_SIZE;public:Stack(); /初始化/int *InsortMiGong(); /輸入迷宮(即一個二維數(shù)組)void FindPath(int ab10); /找出迷宮的出路;Stack:Stack() /初始化rrow=0;ccolm=0;top=-1;count=1;minlenght=MAX_SIZE;/*int * Stack:InsortMiGong() /輸入迷宮(即一個二維數(shù)組)int row=1,colm=1;while(true)cout<<"請輸入迷宮的行數(shù)和列數(shù)

18、:"cin>>row>>colm;if(row<=0|colm<=0)cout<<"輸入錯誤!請重新輸入:"<<endl;rrow=row;ccolm=colm;continue;elserrow=row;ccolm=colm;break;int *mg;cout<<"請輸入迷宮矩陣(只有0和1兩個數(shù)構(gòu)成):"for(int i=0;i<row;i+)for(int j=0;j<colm;j+)cin>>mgij;return mg;*/void S

19、tack:FindPath(int ab10) /找出迷宮的出路int a,b,di,find,k;top+;stacktop.x=1;stacktop.y=1;stacktop.di=-1;ab11=-1;while(top>-1)a=stacktop.x;b=stacktop.y;di=stacktop.di;if(a=8&&b=8)cout<<count+<<":"<<endl;for(int k=0;k<=top;k+)cout<<"("<<stackk.x&

20、lt;<","<<stackk.y<<")"if(!(k+1)%15)cout<<endl;cout<<endl;if(top+1<minlenght)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(di<8&&!find)di+;switch(di)c

21、ase 0:a=stacktop.x-1;b=stacktop.y;break;case 1:a=stacktop.x;b=stacktop.y+1;break;case 2:a=stacktop.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-;cout<<endl;cout<