这个算法自己在学习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
}
