c語言遞歸函數(shù)穿越迷宮 c語言實現(xiàn)遞歸函數(shù)

關(guān)于C++迷宮問題，尋找一條通路穿越迷宮（找到一條即可）。要求寫出一個遞歸程序來穿越迷宮。

題目有問題：如何指定迷宮的起點和終點。

創(chuàng)新互聯(lián)專注于企業(yè)網(wǎng)絡(luò)營銷推廣、網(wǎng)站重做改版、仁布網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5技術(shù)、商城網(wǎng)站建設(shè)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為仁布等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

我這里假設(shè)迷宮某個邊界位置是起點，(x, y)是否是終點要用GotGoal(x, y)函數(shù)判斷。

核心函數(shù)

void DFS(char *m, int height, int width, int x, int y, int now_dir)

這里m是一個一維數(shù)組，表示迷宮。格點x, y的信息是m[y * width + x]

比如3行4列的迷宮

####

#...

..##

在m里就是#####.....##，每一行緊接著上一行。

height 迷宮高度

width 迷宮寬度

x是當(dāng)前位置橫坐標(biāo)。右邊是正方向。

y是當(dāng)前位置縱坐標(biāo)。下方是正方向。

now_dir是是當(dāng)前的方向。你需要給上下左右4個方向規(guī)定一個編號。

比如

int?dir_list[4][2]?=?{

{-1,?0},?//?地圖左

{0,?-1},?//?地圖上

{1,?0},??//?地圖右

{0,?1}???//?地圖下

};

//?第一個數(shù)表示恒坐標(biāo)變化量，第二個數(shù)表示縱坐標(biāo)變化量

那么對于當(dāng)前方向now_dir，“摸著右手邊的墻”的探索方向編號依次是（可以參照上面dir_list的注釋來理解）

(now_dir + 1) % 4 當(dāng)前方向右側(cè)

(now_dir + 0) % 4 當(dāng)前方向

(now_dir - 1 + 4) % 4 當(dāng)前方向左側(cè)

(now_dir - 2 + 4) % 4 當(dāng)前方向反方向（回頭）。（這里要+4是為了防止now_dir減去數(shù)字后變成負數(shù)，負數(shù)除以4的余數(shù)還是負數(shù)）。

使用DFS的方法：

先將地圖信息保存到char數(shù)組里，作為DFS函數(shù)第一參數(shù)

將迷宮入口橫坐標(biāo)保存到x參數(shù)，縱坐標(biāo)保存到y(tǒng)參數(shù)

將剛進入迷宮的方向的編號（dir_list的第一下標(biāo)）保存到now_dir

DFS的基本實現(xiàn)（偽代碼）

void?DFS(char?*m,?int?height,?int?width,?int?x,?int?y,?int?now_dir)

{

int?turn?=?0;

int?new_dir;

int?new_x;

int?new_y;

if?(GotGoal(x,?y)?)?//?如果當(dāng)前位置是終點

return;

m[y?*?width?+?x]?=?'X';?//?占據(jù)當(dāng)前位置

PrintMap(m,?height,?width);?//?打印地圖當(dāng)前狀態(tài)

for?(turn?=?1;?=?-2;?turn--)?//?依次循環(huán)4個方向：右、前、左、回頭

{

new_dir?=?(now_dir?+?turn?+?4)?%?4;?//?計算新方向的編號

new_x?=?x?+?dir_list[new_dir][0];

new_y?=?y?+?dir_list[new_dir][1];?//?計算出“如果要走新方向，則下一步的位置”

if?(new_x??0?||?new_x?=?width)//?如果走出左右邊界

continue;

if?(new_y??0?||?new_y?=?height)?//?如果走出上下邊界

continue;

if?('#'?==?m[new_y?*?width?+?new_x])?//?如果下一步是是墻

continue;

DFS(m,?height,?width,?new_x,?new_y,?new_dir);

}

return;

}

注意：

這個問題由于不涉及最短路，而且每走一步都算走過，包括走進了死胡同。因此這個問題完全不需要用遞歸，實際上程序也不可能回溯，因為每一步都是對的。直接用for或while循環(huán)就行了。用遞歸，當(dāng)路線比較長時，可能超過操作系統(tǒng)限制而報錯。

對于有環(huán)路的迷宮，程序會死循環(huán)。

如果要判斷出死循環(huán)的情況，需要一個額外的數(shù)組int m_arrived[][4]，保存每個位置的每個方向是否走過。一開始都是0，走過m[i]且方向是dir的時候，m_arrived[i][dir] = 1即可。

有不明白的地方請追問。

如何用C語言編寫一個迷宮程序？

#include graphics.h

#include stdlib.h

#include stdio.h

#include conio.h

#include dos.h

#define N 20/*

迷宮的大小，可改變

*/

int oldmap[N][N];/*

遞歸用的數(shù)組

,

用全局變量節(jié)約時間

*/

int yes=0;/*yes

是判斷是否找到路的標(biāo)志

,1

找到，

沒找到

*/

int way[100][2],wayn=0;/*way

數(shù)組是顯示路線用的

,wayn

是統(tǒng)計走了幾個格

子

*/

void Init(void);/*

圖形初始化

*/

void Close(void);/*

圖形關(guān)閉

*/

void DrawPeople(int *x,int *y,int n);/*

畫人工探索物圖

*/

void PeopleFind(int (*x)[N]);/*

人工探索

*/

void

WayCopy(int

(*x)[N],int

(*y)[N]);/*

為了

8

個方向的遞歸，把舊迷宮圖

拷貝給新數(shù)組

*/

int FindWay(int (*x)[N],int i,int j);/*

自動探索函數(shù)

*/

void MapRand(int (*x)[N]);/*

隨機生成迷宮函數(shù)

*/

void PrMap(int (*x)[N]);/*

輸出迷宮圖函數(shù)

*/

void Result(void);/*

輸出結(jié)果處理

*/

void Find(void);/*

成功處理

*/

void NotFind(void);/*

失敗處理

*/

void main(void)/*

主函數(shù)

*/

{

int map[N][N]; /*

迷宮數(shù)組

*/

char ch;

clrscr();

printf("\n Please select hand(1) else auto\n");/*

選擇探索方式

*/

scanf("%c",ch);

Init(); /*

初始化

*/

MapRand(map);/*

生成迷宮

*/

PrMap(map);/*

顯示迷宮圖

*/

if(ch=='1')

PeopleFind(map);/*

人工探索

*/

else

FindWay(map,1,1);/*

系統(tǒng)自動從下標(biāo)

1,1

的地方開始探索

*/

Result();/*

輸出結(jié)果

*/

Close();

}

void Init(void)/*

圖形初始化

*/

{

int gd=DETECT,gm;

initgraph(gd,gm,"c:\\tc"); }

void DrawPeople(int *x,int *y,int n)/*畫人工控制圖*/ {/*如果將以下兩句注釋掉，則顯示人工走過的路徑，*/

setfillstyle(SOLID_FILL,WHITE); /*設(shè)置白色實體填充樣式*/ bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6); /*恢復(fù)原通路*/

switch(n)/*判斷x,y的變化，8個方向的變化*/ {

case 1: (*x)--;break; /*上*/

case 2: (*x)--;(*y)++;break /*右上*/ case 3: (*y)++;break; /*右*/

case 4: (*x)++;(*y)++;break; /*右下*/ case 5: (*x)++;break; /*下*/

case 6: (*x)++;(*y)--;break; /*左下*/ case 7: (*y)--;break; /*左*/

case 8: (*x)--;(*y)--;break; /*左上*/ }

setfillstyle(SOLID_FILL,RED);/*新位置顯示探索物*/

bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6); }

void PeopleFind(int (*map)[N])/*人工手動查找*/ {

int x,y;

char c=0;/*接收按鍵的變量*/ x=y=1;/*人工查找的初始位置*/ setcolor(11);

line(500,200,550,200); outtextxy(570,197,"d"); line(500,200,450,200); outtextxy(430,197,"a"); line(500,200,500,150); outtextxy(497,130,"w"); line(500,200,500,250); outtextxy(497,270,"x"); line(500,200,450,150); outtextxy(445,130,"q"); line(500,200,550,150); outtextxy(550,130,"e"); line(500,200,450,250); outtextxy(445,270,"z"); line(500,200,550,250);

outtextxy(550,270,"c");/*以上是畫8個方向的控制介紹*/

setcolor(YELLOW);

outtextxy(420,290,"Press 'Enter' to end");/*壓回車鍵結(jié)束*/ setfillstyle(SOLID_FILL,RED);

bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置顯示*/ while(c!=13)/*如果按下的不是回車鍵*/ {

c=getch();/*接收字符后開始各個方向的探索*/ if(c=='w'map[x-1][y]!=1) DrawPeople(x,y,1);/*上*/ else if(c=='e'map[x-1][y+1]!=1) DrawPeople(x,y,2);/*右上*/ else if(c=='d'map[x][y+1]!=1) DrawPeople(x,y,3);/*右*/ else if(c=='c'map[x+1][y+1]!=1) DrawPeople(x,y,4);/*右下*/ else if(c=='x'map[x+1][y]!=1) DrawPeople(x,y,5);/*下*/ else if(c=='z'map[x+1][y-1]!=1) DrawPeople(x,y,6); /*左下*/ else if(c=='a'map[x][y-1]!=1) DrawPeople(x,y,7); /*左*/ else if(c=='q'map[x-1][y-1]!=1) DrawPeople(x,y,8); /*左上*/ }

setfillstyle(SOLID_FILL,WHITE); /*消去紅色探索物，恢復(fù)原迷宮圖*/ bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6); if(x==N-2y==N-2)/*人工控制找成功的話*/ yes=1; /*如果成功標(biāo)志為1*/ }

void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷貝迷宮數(shù)組 */ {

int i,j;

for(i=0;iN;i++) for(j=0;jN;j++) oldmap[i][j]=map[i][j]; }

int FindWay(int (*map)[N],int i,int j)/*遞歸找路*/ {

if(i==N-2j==N-2)/*走到出口*/ {

yes=1;/*標(biāo)志為1,表示成功*/ return; }

map[i][j]=1;/*走過的地方變?yōu)?*/ WayCopy(oldmap,map); /*拷貝迷宮圖*/

if(oldmap[i+1][j+1]==0!yes)/*判斷右下方是否可走*/ {

FindWay(oldmap,i+1,j+1); if(yes)/*如果到達出口了，再把值賦給顯示路線的way數(shù)組,也正是這個原因,所以具體路線是從最后開始保存*/ { way[wayn][0]=i; way[wayn++][1]=j; return; } }

WayCopy(oldmap,map);

if(oldmap[i+1][j]==0!yes)/*判斷下方是否可以走,如果標(biāo)志yes已經(jīng)是1也不用找下去了*/ {

FindWay(oldmap,i+1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }

WayCopy(oldmap,map);

if(oldmap[i][j+1]==0!yes)/*判斷右方是否可以走*/ {

FindWay(oldmap,i,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }

WayCopy(oldmap,map);

if(oldmap[i-1][j]==0!yes)/*判斷上方是否可以走*/ {

FindWay(oldmap,i-1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }

WayCopy(oldmap,map);

if(oldmap[i-1][j+1]==0!yes)/*判斷右上方是否可以走*/ {

FindWay(oldmap,i-1,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }

WayCopy(oldmap,map);

if(oldmap[i+1][j-1]==0!yes)/*判斷左下方是否可以走*/ {

FindWay(oldmap,i+1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }

WayCopy(oldmap,map);

if(oldmap[i][j-1]==0!yes)/*判斷左方是否可以走*/ {

FindWay(oldmap,i,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }

WayCopy(oldmap,map);

if(oldmap[i-1][j-1]==0!yes)/*判斷左上方是否可以走*/ {

FindWay(oldmap,i-1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }

return; }

void MapRand(int (*map)[N])/*開始的隨機迷宮圖*/ {

int i,j;

cleardevice();/*清屏*/

randomize(); /*隨機數(shù)發(fā)生器*/ for(i=0;iN;i++) {

for(j=0;jN;j++) { if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈為墻壁*/ map[i][j]=1; else if(i==1j==1||i==N-2j==N-2)/*出發(fā)點與終點表示為可走的*/ map[i][j]=0; else map[i][j]=random(2);/*其它的隨機生成0或1*/ } } }

void PrMap(int (*map)[N])/*輸出迷宮圖*/ {

int i,j;

for(i=0;iN;i++) for(j=0;jN;j++) if(map[i][j]==0) { setfillstyle(SOLID_FILL,WHITE);/*白色為可走的路*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6); } else { setfillstyle(SOLID_FILL,BLUE);/*藍色為墻壁*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);

} }

void Find(void)/*找到通路*/ {

int i;

setfillstyle(SOLID_FILL,RED);/*紅色輸出走的具體路線*/ wayn--;

for(i=wayn;i=0;i--) {

bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+ way[i][1]*15+6,50+way[i][0]*15+6); sleep(1);/*控制顯示時間*/ }

bar(100+(N-2)*15-6,50+(N-2)*15-6,100+ (N-2)*15+6,50+(N-2)*15+6); /*在目標(biāo)點標(biāo)紅色*/ setcolor(GREEN);

settextstyle(0,0,2);/*設(shè)置字體大小*/ outtextxy(130,400,"Find a way!"); }

void NotFind(void)/*沒找到通路*/ {

setcolor(GREEN);

settextstyle(0,0,2);/*設(shè)置字體大小*/ outtextxy(130,400,"Not find a way!"); }

void Result(void)/*結(jié)果處理*/ {

if(yes)/*如果找到*/ Find();

else/*沒找到路*/ NotFind(); getch(); }

void Close(void)/*圖形關(guān)閉*/ {

closegraph(); }

求解c語言一遞歸迷宮問題

給你給偽算法：（設(shè)坐標(biāo)為x,y,坐標(biāo)向右和下延生。）

函數(shù)：

｛

判斷當(dāng)前是不是（7,7)，如果是，表示走出迷宮。打印軌跡

1 嘗試往左先走一步（x-1，如果x小于0，或者對應(yīng)位置標(biāo)識為阻塞）

2 1如果成功，用本函數(shù)遞歸調(diào)用左走一步的坐標(biāo)，并記下當(dāng)前位置到軌跡列表。

3 嘗試往前先走一步（y+1，如果y小于0，或者對應(yīng)位置標(biāo)識為阻塞）

4 3如果成功，用本函數(shù)遞歸調(diào)用前走一步的坐標(biāo),并記下當(dāng)前位置到軌跡列表。

5 嘗試往右先走一步（x+1，如果x小于0，或者對應(yīng)位置標(biāo)識為阻塞）

6 5如果成功，用本函數(shù)遞歸調(diào)用前走一步的坐標(biāo),并記下當(dāng)前位置到軌跡列表。

如果是（0，0），表示沒有合適的路徑可走出迷宮。

如果不是（0，0），將軌跡列表最后一位彈出。

｝

新聞名稱：c語言遞歸函數(shù)穿越迷宮 c語言實現(xiàn)遞歸函數(shù)
文章URL：http://muchs.cn/article32/doeepsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、品牌網(wǎng)站設(shè)計、自適應(yīng)網(wǎng)站、企業(yè)網(wǎng)站制作、搜索引擎優(yōu)化、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)