Object-c 使用栈实现迷宫

• 关于本例子中用到的栈结构请参看：https://www.jianshu.com/p/c941b224a69d

• 迷宫分析：
  迷宫通常是用一个二维数组来表示，通路以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个栈与一个与迷宫数组规格一样的数组,一个用来有存储下一步待走的索引，以上图为例当前s在二维数组中的索引下标为（3，3），下一步有可能走（3，2）与（2，3）那么栈中就存放（3，2）与（2，3）（为了存放方便可以声明一个对象Cell内含x,y2个成员变量来表示在二维数组的索引）。
• 数组在寻找迷宫路径的过程中使用，它的初始值只记住起点与终点位置，数组的行列应与迷宫原始数组保持一致。其他的点都是待寻找的点，寻找时都要探索当前点上、下、左、右四个方位直到出现下面三种情况之一则停止当前点的探索：
  已经访问过
  已经到边界了
  当前点为迷宫中的樯（不通点）
  为了记住尝试过的路径，需要将当前已经走过的点在数组对应的下标中的状态改为已经访问过，这个状态值非常重要一定要与连通点标记0和终点标记e区别开来（本例中标记为' . '）。置成这个标记主要目的是为了防止重复寻找陷入无穷的递归当中。存放的点需满足下面规则：
  连通的点
  终点
  开始时这个数组的值如下：

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

• 下面是本迷宫栈与数组每一步的存入情况

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--------经过的路径结点坐标 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--------  无出路 寻找失败：node 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]; //将最后一个结点置为走过，真实的路径可以不需要此步
    [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