關(guān)于本例子中用到的棧結(jié)構(gòu)請參看：http://www.itdecent.cn/p/c941b224a69d
迷宮分析：
迷宮通常是用一個二維數(shù)組來表示，通路以0表示，不通以1表示，出口位置以e表示，起點為s表示（如下圖所示）。
| 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | e | 1 |
| 1 | 0 | 0 | s | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
- 程序中使用1個棧與一個與迷宮數(shù)組規(guī)格一樣的數(shù)組,一個用來有存儲下一步待走的索引，以上圖為例當(dāng)前s在二維數(shù)組中的索引下標(biāo)為（3，3），下一步有可能走（3，2）與（2，3）那么棧中就存放（3，2）與（2，3）（為了存放方便可以聲明一個對象Cell內(nèi)含x,y2個成員變量來表示在二維數(shù)組的索引）。
- 數(shù)組在尋找迷宮路徑的過程中使用，它的初始值只記住起點與終點位置，數(shù)組的行列應(yīng)與迷宮原始數(shù)組保持一致。其他的點都是待尋找的點，尋找時都要探索當(dāng)前點上、下、左、右四個方位直到出現(xiàn)下面三種情況之一則停止當(dāng)前點的探索：
已經(jīng)訪問過
已經(jīng)到邊界了
當(dāng)前點為迷宮中的檣（不通點）
為了記住嘗試過的路徑，需要將當(dāng)前已經(jīng)走過的點在數(shù)組對應(yīng)的下標(biāo)中的狀態(tài)改為已經(jīng)訪問過，這個狀態(tài)值非常重要一定要與連通點標(biāo)記0和終點標(biāo)記e區(qū)別開來（本例中標(biāo)記為' . '）。置成這個標(biāo)記主要目的是為了防止重復(fù)尋找陷入無窮的遞歸當(dāng)中。存放的點需滿足下面規(guī)則：
連通的點
終點
開始時這個數(shù)組的值如下：
| 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | e | 1 |
| 1 | 1 | 1 | s | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
- 下面是本迷宮棧與數(shù)組每一步的存入情況
QQ20200510-200150@2x.png
*核心 代碼如下：
-(void) pushUnVisited:(NSInteger)x y:(NSInteger)y{
Cell* cell = [[Cell alloc] init:x y:y];
NSString* tmp = [[self.storeArray objectAtIndex:x] objectAtIndex:y];
if ([tmp isEqualToString:@"0"] || [tmp isEqualToString:@"2"]) {
[self.mazeStack push:cell];
NSLog(@"78------:入棧x：%ld y:%ld",x,y);
}
}
-(void) queryPath{
NSInteger row = 0;
NSInteger col = 0;
while (!([self.curCell isEqual:self.exitCell])) {
row = self.curCell.x;
col = self.curCell.y;
NSLog(@"53--------經(jīng)過的路徑結(jié)點坐標(biāo) x:%ld y:%ld",row,col);
if(![self.curCell isEqual:self.enterCell]){
NSMutableArray* rowarray = [self.storeArray objectAtIndex:row];
//代表訪問過了
[rowarray replaceObjectAtIndex:col withObject:@"."];
}
[self pushUnVisited:row - 1 y:col];
[self pushUnVisited:row + 1 y:col];
[self pushUnVisited:row y:col - 1];
[self pushUnVisited:row y:col + 1];
if([self.mazeStack isEmpty]){
NSLog(@"83-------- 無出路 尋找失?。簄ode x:%ld y:%ld",row,col);
return;
}else{
self.curCell =(Cell*)[self.mazeStack pop];
NSLog(@"105-------出棧x：%ld y :%ld 棧大小:%ld",self.curCell.x,self.curCell.y,[self.mazeStack count]);
}
}
printf("90-------尋找成功 x:%ld y:%ld:\n",self.curCell.x,self.curCell.y);
NSMutableArray* rowarray = [self.storeArray objectAtIndex:self.curCell.x]; //將最后一個結(jié)點置為走過，真實的路徑可以不需要此步
[rowarray replaceObjectAtIndex:self.curCell.y withObject:@"."];
[self printPath];
}
-(void) printPath{
for (int i = 0; i < 5; i ++) {
for (int j = 0 ; j < 6; j ++){
NSString* tmp = [[self.storeArray objectAtIndex:i] objectAtIndex:j];
printf(" %s ",[tmp UTF8String]);
}
printf("\n");
}
}
-
測試效果如下圖：
QQ20200510-195335@2x.png
