數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮問題

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮問題迷宮求解問題題目描述用一個(gè)m×n的矩陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)給定的迷宮，求出找到的第一條從入口到出口的通路，或得到?jīng)]有通路的結(jié)論。我們指定:迷宮的入口為矩陣的左上角（1,1），迷宮的出口為右下角（m,n）;路徑的探索順序依次為"東南西北"（即：右下左上）。輸入第一行輸入兩個(gè)整數(shù)，空格間隔，分別表示矩陣的行數(shù)m和列數(shù)n；接下來的連續(xù)m行，輸入迷宮矩陣的信息。輸出求得的通路以三元組(i,j,d)的形式輸出。其中：i,j指示迷宮的一個(gè)坐標(biāo);d表示走到下一坐標(biāo)的方向(數(shù)字1表示東，數(shù)字2表示南，數(shù)字3表示西，數(shù)字4表示北);終點(diǎn)d值為0。樣例輸入98001000100010001000001101011100100001000001000101011110011100010111000000樣例輸出(1,1,1)(1,2,2)(2,2,2)(3,2,3)(3,1,2)(4,1,2)(5,1,1)(5,2,1)(5,3,2)(6,3,1)(6,4,1)(6,5,4)(5,5,1)(5,6,1)(5,7,2)(6,7,2)(7,7,2)(8,7,2)(9,7,1)(9,8,0)。ok，具體的題目就如上了大概意思呢，我們輸入一個(gè)全是0或1的二維數(shù)組，要輸出一堆三元組，從左上角開始走，到右下角為出口，三元組：前兩個(gè)數(shù)字為坐標(biāo)，最后的數(shù)字為移動(dòng)的方向，這里東南西北分別對(duì)應(yīng)1234本題的本意是考驗(yàn)對(duì)棧的操作，以及對(duì)遞歸的運(yùn)用，我們上代碼，后分析。#include<stdio.h>#include<stdlib.h>#defineerror(str)fprintf(stderr,"%s",str),exit(1)typedefstructnode{inti,j,k;structnode*next;}stack;stack*s;//這里直接聲明stack*sstack*creat({stack*s=(stack*)malloc(sizeof(stack));s->i=0,s->j=0,s->k=0,s->next=NULL;returns;}intisempty(stack*s){returns->next==NULL;}voidpush(stack*s,inti,intj,intk){stack*front=(stack*)malloc(sizeof(stack));front->i=i,front->j=j,front->k=k;front->next=s->next;s->next=front;}voidpop(stack*s){if(isempty(s))error("isalreadyempty");stack*front=s->next;s->next=s->next->next;free(front);}intfindway(inta[][100],intei,intej,intsi,intsj,inti,intj)//這里采用遞歸算法尋路{inte=0;//用e做flaga[i][j]=2;//這里主要是用于替換對(duì)任何數(shù)字都可以if(i==ei&&j==ej)e=1;if(e!=1&&j+1<=ej&&a[i][j+1]==0)//往東{push(s,i,j,1);if(findway(a,ei,ej,si,sj,i,j+1)==1)//這里通過遞歸繼續(xù)整個(gè)算法return1;}if(e!=1&&i+1<=ei&&a[i+1][j]==0)//往南{push(s,i,j,2);if(findway(a,ei,ej,si,sj,i+1,j)==1)return1;}if(e!=1&&j-1>=sj&&a[i][j-1]==0)//往西{push(s,i,j,3);if(findway(a,ei,ej,si,sj,i,j-1)==1)return1;}if(e!=1&&i-1>=si&&a[i-1][j]==0)//往北{push(s,i,j,4);if(findway(a,ei,ej,si,sj,i-1,j)==1)return1;}if(e!=1){a[i][j]==0;pop(s);}returne;}voidshow(stack*s){if(s->next)show(s->next);if(s->i)printf("(%d,%d,%d)",s->i,s->j,s->k);}intmain({s=creat(;//stack*s以在前面聲明過inti,j,l,k;scanf("%d%d",&i,&j);inta[100][100];for(l=1;l<=i;l++)for(k=1;k<=j;k++)scanf("%1d",&a[l][k]);if(findway(a,i,j,1,1,1,1)==1){push(s,i,j,0);//這里是最后的情況，輸出位置和0.show(s);}return0;}。首先我們需要對(duì)棧的操作函數(shù)，這里我們要用到創(chuàng)建，入棧，出棧，判空，這些函數(shù)都很容易寫，便不細(xì)講。博主的思路是通過暴力遍歷每一條的方式去找到出路，因此是一個(gè)全程的遞歸過程，并且我對(duì)算法加了返回值，是為了最后的if判斷，好，接下來我們細(xì)看算法思路我剛開始想著是直接對(duì)數(shù)組進(jìn)行蠻橫的右下探索，但是這條路實(shí)質(zhì)上并沒有用到棧的性質(zhì)，后來結(jié)合一些朋友的幫助想到了不斷的遞歸的過程。這里的函數(shù)我也很形象的命名為findway，那么首先，我們給整個(gè)二維數(shù)組設(shè)置一個(gè)外環(huán)的全為1的套，這樣就等于堵死了在外的所有路，然鵝實(shí)際上，看代碼不難發(fā)現(xiàn)我們并沒有真的設(shè)置套，而是設(shè)置了范圍，同時(shí)我們的數(shù)值都是從索引1開始取的，這樣就夠了這樣一個(gè)結(jié)構(gòu)如圖：（a代指各個(gè)數(shù)字）而我們核心算法就是同歸遞歸遍歷所有的路，我們從第一條路舉例開始分析，（以題中所給數(shù)字）我們進(jìn)入算法，首先，從0開始，判斷進(jìn)入下一層函數(shù)，這時(shí)候是往東，因此到了坐標(biāo)（1,2），入棧，接著往南，進(jìn)入坐標(biāo)（2,2），入棧，又往南進(jìn)入（3,2），接著兩次往東到（3,4）不斷的入棧，那么這時(shí)候有朋友就要問了，從判斷角度來說，往西在往北的前面這意味著他又回到之前的位置了，進(jìn)而又往東往復(fù)循環(huán)。朋友，不會(huì)的，注意看算法前有一句a[i][j]=2;//這里主要是用于替換對(duì)任何數(shù)字都可以，這個(gè)數(shù)字會(huì)覆蓋你走過的每步，也就是說你走過之后他就不再是0了而是2，所以他不符合回去的條件，只能選擇往北走，到（2,4）接著，往東兩次，往北一次，往西三次到了（1,4）此時(shí)的矩陣是這樣的。我們?cè)诩t點(diǎn)這。這時(shí)候沒有路了，那么我們的e就不等于1了于是出棧，接著每一層遞歸都從if判斷條件跳出，一個(gè)一個(gè)出棧一直出到剛開始遞歸入口，從下一個(gè)if進(jìn)去繼續(xù)判斷，總體就是這樣的過程，如果對(duì)遞歸運(yùn)用不太熟練可能理解有點(diǎn)苦難，不過多看幾遍就好，應(yīng)該沒什么問題，這里博主已經(jīng)將語(yǔ)言化為最簡(jiǎn)模式講出來了，這樣一直遍歷，只到最后到了范圍，這是e等于1直接return，又一路return出來如果是到最后了，那么我們遞歸入口的返回值也是1，這時(shí)候我們對(duì)入棧的數(shù)遞歸輸出就好。這里遞歸輸出是因?yàn)闂５男再|(zhì)是一步一步往里存的，而我們的出棧操作只能看到頂也就是最后存入的，所以我們遞歸讓他從剛開始存入的開始輸