iOS 广度优先搜索算法 实现扫雷自动‘翻牌’功能

这个算法自己在学习iOS开发做的一个扫雷游戏，并且已经上了AppStore ，但是之后一直在忙没顾得上优化，如果大家发现什么bug或者可以优化的地方，希望各位看官不吝赐教多多反馈交流。下面进入正题，实现这个功能需要自定义5个类，说明如下：

1.单个格子模型类，用于记录格子的坐标、遍历状态等状态；
2.图的模型类，用于记录行列数量和当前翻开的状态；
3.基于数组的队列类，广搜算法中要使用的队列，先进先出；（如果改为栈可以实现深度优先搜索）
4.计算周边点的工具类，只有一个方法实现根据某点获取其周边所有的点，并返回一个数组；
5.最重要的广度优先搜索算法类

定义一个格子模型

#import <Foundation/Foundation.h>
/// 点的坐标
typedef struct {
    int  x;
    int  y;
}ItemIndex;

@interface QSItem : NSObject <NSCoding>
/**是否是雷*/
@property(nonatomic,assign,getter=isMine)BOOL mine;
/**是否已经打开*/
@property(nonatomic,assign,getter=isOpened)BOOL opened;
/**周边雷数量*/
@property(nonatomic,assign) NSInteger arroundMineNumber;
/**是否遍历过*/
@property(nonatomic,assign,getter=isTraveled)BOOL traveled;
/**是否标记为雷*/
@property(nonatomic,assign,getter=isSignMine)BOOL signMine;
/**在地图中的坐标*/
@property(nonatomic,assign)ItemIndex indexInGraph;
@end
#import "QSItem.h"

@implementation QSItem

- (instancetype)initWithCoder:(NSCoder *)aDecoder{
    self = [super init];
    if (self) {
        [aDecoder decodeBoolForKey:@"mine"];
        [aDecoder decodeBoolForKey:@"opened"];
        [aDecoder decodeBoolForKey:@"traveled"];
        [aDecoder decodeBoolForKey:@"signMine"];
        [aDecoder decodeIntegerForKey:@"arroundMineNumber"];
        [aDecoder decodeValueOfObjCType:@encode(ItemIndex) at:&_indexInGraph];
    }
    return self;
}

- (void)encodeWithCoder:(NSCoder *)aCoder{
    [aCoder encodeBool:self.mine forKey:@"mine"];
    [aCoder encodeBool:self.opened forKey:@"opened"];
    [aCoder encodeBool:self.traveled forKey:@"traveled"];
    [aCoder encodeBool:self.signMine forKey:@"signMine"];
    [aCoder encodeInteger:self.arroundMineNumber forKey:@"arroundMineNumber"];
    [aCoder encodeValueOfObjCType:@encode(ItemIndex) at:&_indexInGraph];
}


@end

定义一个图的模型

#import <Foundation/Foundation.h>

@interface QSGraph : NSObject<NSCoding>
/**地图数组*/
@property(nonatomic,strong) NSArray *itemArray;
/**地图宽度*/
@property(nonatomic,assign) NSInteger width;
/**地图高度*/
@property(nonatomic,assign) NSInteger heigth;
/**总雷数*/
@property(nonatomic,assign) NSUInteger totalMinesNumber;
/**已打开的总数*/
@property(nonatomic,assign) NSInteger totalOpenedNumber;

@end
#import "QSGraph.h"

@implementation QSGraph

- (instancetype)initWithCoder:(NSCoder *)aDecoder{
    self = [super init];
    if (self) {
        [aDecoder decodeObjectForKey:@"itemArray"];
        [aDecoder decodeIntegerForKey:@"totalMinesNumber"];
        [aDecoder decodeIntegerForKey:@"width"];
        [aDecoder decodeIntegerForKey:@"heigth"];
    }
    return self;
}

- (void)encodeWithCoder:(NSCoder *)aCoder{
    [aCoder encodeObject:self.itemArray forKey:@"itemArray"];
    [aCoder encodeInteger:self.totalMinesNumber forKey:@"totalMinesNumber"];
    [aCoder encodeInteger:self.width forKey:@"width"];
    [aCoder encodeInteger:self.heigth forKey:@"heigth"];
}

//重写width,height方法,最小为3,小于则返回-1
- (void)setWidth:(NSInteger)width
{
    if (width >= 3) {
        _width = width;
    }else
    {
        _width = -1;
    }
}

- (void)setHeigth:(NSInteger)heigth
{
    if (heigth >= 3) {
        _heigth = heigth;
    }else
    {
        _heigth = -1;
    }
}

@end

定义一个获取周边8个点的工具类

#import <Foundation/Foundation.h>
#import "QSGraph.h"
#import "QSItem.h"

@interface QSAroundMines : NSObject
/**根据数组判断周边 对象*/
+ (NSArray *)getAroundMinesArrayByItem:(QSItem *)item graph:(QSGraph *)graph;
@end
#import "QSAroundMines.h"

@implementation QSAroundMines

+ (NSArray *)getAroundMinesArrayByItem:(QSItem *)item graph:(QSGraph *)graph
{
    //可变数组
    NSMutableArray *mutableArray = [NSMutableArray array];
    //获取x,y坐标
    int x = item.indexInGraph.x;
    int y = item.indexInGraph.y;
    //循环判断周边点,跳过边界和自身
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            //过滤自身和越界
            if(
               (i == 0 && j == 0)                    //跳过本身
               || (x == 0 && i == -1)                //跳过-1行
               || (y == 0 && j == -1)                //跳过-1列
               || ((y == graph.width - 1) && j == 1) //跳过+1列
               || ((x == graph.heigth - 1) && i == 1)//跳过+1行
               ) continue;
            //没有越界则将周边item加入到数组中
            NSInteger index = (x + i) * graph.width + y + j;
            QSItem *aroundItem = graph.itemArray[index];
            [mutableArray addObject:aroundItem];
        }
    }
    return mutableArray;
}

@end

定义一个队列类

#import <Foundation/Foundation.h>
#import "QSItem.h"

@interface QSQueue : NSObject
/**队列长度*/
@property(nonatomic,assign)NSUInteger count;
/// 单例生成一个queue对象
+ (QSQueue *) sharedQueue;
/**插入队尾元素*/
- (void)insertValueAtTailOfQueue:(QSItem*)item;
/**弹出队头元素*/
- (QSItem *)getValueOfHeaderOfQueue;
@end
#import "QSQueue.h"

@interface QSQueue ()
//队列内置数组
@property(nonatomic,strong) NSMutableArray *array;
@end

@implementation QSQueue

+ (QSQueue *)sharedQueue
{
    static QSQueue *queue = nil;
    if (queue == nil) {
        queue = [[QSQueue alloc] init];
    }
    return queue;
}

//懒加载数组
- (NSMutableArray *)array
{
    if (!_array) {
        _array = [NSMutableArray array];
    }
    return _array;
}
/// 队列长度
-(NSUInteger)count
{
    return self.array.count;
}
/// 插入一个元素
- (void)insertValueAtTailOfQueue:(QSItem *)item
{
    [self.array addObject:item];
    //判断插入的元素是否在队列中已存在,如果存在则删除,不存在则插入
    for (QSItem *itemInArray in self.array) {
        if (itemInArray != self.array.lastObject) {
            if (item == itemInArray) {
                [self.array removeObject:item];
            }
        }
    }
}
/// 弹出一个元素
- (QSItem *)getValueOfHeaderOfQueue
{
    QSItem *item = self.array.firstObject;
        [self.array removeObjectAtIndex:0];
    return item;
}

@end

BFS核心算法

+ (void)bfsFunction:(QSGraph *)graph value:(QSItem *)item
{
    //初始化一个队列
    QSQueue *queue = [QSQueue sharedQueue];
    //第一步:将结点加入到队列中
    [queue insertValueAtTailOfQueue:item];
    while (queue.count != 0) {
        //从队列头弹出一个元素
        QSItem *itemInQueue = [queue getValueOfHeaderOfQueue];
        //获取弹出元素周边结点数组(无自身,不越界)
        NSArray *array = [QSAroundMines getAroundMinesArrayByItem:itemInQueue graph:graph];
        for (QSItem *itemInArray in array) {
            //遍历过 或 雷 或 打开了 则跳过
            if (itemInArray.isTraveled == YES || itemInArray.isMine == YES || itemInArray.isOpened == YES){
                continue;
            }
            //周边雷数为0则加入队列
            if (itemInArray.arroundMineNumber == 0) {
                itemInArray.opened = YES;
                itemInArray.traveled = YES;
                [queue insertValueAtTailOfQueue:itemInArray];
            }
            //周边雷数不为0,不加入队列,但设置为遍历过,并打开
            else{
                itemInArray.opened = YES;
                itemInArray.traveled = YES;
            }
        }//for
    }//while
}