這個(gè)算法自己在學(xué)習(xí)iOS開發(fā)做的一個(gè)掃雷游戲，并且已經(jīng)上了AppStore 屁使，但是之后一直在忙沒顧得上優(yōu)化配猫，如果大家發(fā)現(xiàn)什么bug或者可以優(yōu)化的地方，希望各位看官不吝賜教多多反饋交流砂豌。下面進(jìn)入正題，實(shí)現(xiàn)這個(gè)功能需要自定義5個(gè)類啥刻，說明如下：
1.單個(gè)格子模型類奸鸯，用于記錄格子的坐標(biāo)、遍歷狀態(tài)等狀態(tài)可帽；
2.圖的模型類，用于記錄行列數(shù)量和當(dāng)前翻開的狀態(tài)窗怒；
3.基于數(shù)組的隊(duì)列類映跟，廣搜算法中要使用的隊(duì)列，先進(jìn)先出扬虚；（如果改為椗叮可以實(shí)現(xiàn)深度優(yōu)先搜索）
4.計(jì)算周邊點(diǎn)的工具類，只有一個(gè)方法實(shí)現(xiàn)根據(jù)某點(diǎn)獲取其周邊所有的點(diǎn)辜昵，并返回一個(gè)數(shù)組荸镊；
5.最重要的廣度優(yōu)先搜索算法類
定義一個(gè)格子模型
#import <Foundation/Foundation.h>
/// 點(diǎn)的坐標(biāo)
typedef struct {
int x;
int y;
}ItemIndex;
@interface QSItem : NSObject <NSCoding>
/**是否是雷*/
@property(nonatomic,assign,getter=isMine)BOOL mine;
/**是否已經(jīng)打開*/
@property(nonatomic,assign,getter=isOpened)BOOL opened;
/**周邊雷數(shù)量*/
@property(nonatomic,assign) NSInteger arroundMineNumber;
/**是否遍歷過*/
@property(nonatomic,assign,getter=isTraveled)BOOL traveled;
/**是否標(biāo)記為雷*/
@property(nonatomic,assign,getter=isSignMine)BOOL signMine;
/**在地圖中的坐標(biāo)*/
@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
定義一個(gè)圖的模型
#import <Foundation/Foundation.h>
@interface QSGraph : NSObject<NSCoding>
/**地圖數(shù)組*/
@property(nonatomic,strong) NSArray *itemArray;
/**地圖寬度*/
@property(nonatomic,assign) NSInteger width;
/**地圖高度*/
@property(nonatomic,assign) NSInteger heigth;
/**總雷數(shù)*/
@property(nonatomic,assign) NSUInteger totalMinesNumber;
/**已打開的總數(shù)*/
@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
定義一個(gè)獲取周邊8個(gè)點(diǎn)的工具類
#import <Foundation/Foundation.h>
#import "QSGraph.h"
#import "QSItem.h"
@interface QSAroundMines : NSObject
/**根據(jù)數(shù)組判斷周邊 對(duì)象*/
+ (NSArray *)getAroundMinesArrayByItem:(QSItem *)item graph:(QSGraph *)graph;
@end
#import "QSAroundMines.h"
@implementation QSAroundMines
+ (NSArray *)getAroundMinesArrayByItem:(QSItem *)item graph:(QSGraph *)graph
{
//可變數(shù)組
NSMutableArray *mutableArray = [NSMutableArray array];
//獲取x,y坐標(biāo)
int x = item.indexInGraph.x;
int y = item.indexInGraph.y;
//循環(huán)判斷周邊點(diǎn),跳過邊界和自身
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加入到數(shù)組中
NSInteger index = (x + i) * graph.width + y + j;
QSItem *aroundItem = graph.itemArray[index];
[mutableArray addObject:aroundItem];
}
}
return mutableArray;
}
@end
定義一個(gè)隊(duì)列類
#import <Foundation/Foundation.h>
#import "QSItem.h"
@interface QSQueue : NSObject
/**隊(duì)列長(zhǎng)度*/
@property(nonatomic,assign)NSUInteger count;
/// 單例生成一個(gè)queue對(duì)象
+ (QSQueue *) sharedQueue;
/**插入隊(duì)尾元素*/
- (void)insertValueAtTailOfQueue:(QSItem*)item;
/**彈出隊(duì)頭元素*/
- (QSItem *)getValueOfHeaderOfQueue;
@end
#import "QSQueue.h"
@interface QSQueue ()
//隊(duì)列內(nèi)置數(shù)組
@property(nonatomic,strong) NSMutableArray *array;
@end
@implementation QSQueue
+ (QSQueue *)sharedQueue
{
static QSQueue *queue = nil;
if (queue == nil) {
queue = [[QSQueue alloc] init];
}
return queue;
}
//懶加載數(shù)組
- (NSMutableArray *)array
{
if (!_array) {
_array = [NSMutableArray array];
}
return _array;
}
/// 隊(duì)列長(zhǎng)度
-(NSUInteger)count
{
return self.array.count;
}
/// 插入一個(gè)元素
- (void)insertValueAtTailOfQueue:(QSItem *)item
{
[self.array addObject:item];
//判斷插入的元素是否在隊(duì)列中已存在,如果存在則刪除,不存在則插入
for (QSItem *itemInArray in self.array) {
if (itemInArray != self.array.lastObject) {
if (item == itemInArray) {
[self.array removeObject:item];
}
}
}
}
/// 彈出一個(gè)元素
- (QSItem *)getValueOfHeaderOfQueue
{
QSItem *item = self.array.firstObject;
[self.array removeObjectAtIndex:0];
return item;
}
@end
BFS核心算法
+ (void)bfsFunction:(QSGraph *)graph value:(QSItem *)item
{
//初始化一個(gè)隊(duì)列
QSQueue *queue = [QSQueue sharedQueue];
//第一步:將結(jié)點(diǎn)加入到隊(duì)列中
[queue insertValueAtTailOfQueue:item];
while (queue.count != 0) {
//從隊(duì)列頭彈出一個(gè)元素
QSItem *itemInQueue = [queue getValueOfHeaderOfQueue];
//獲取彈出元素周邊結(jié)點(diǎn)數(shù)組(無自身,不越界)
NSArray *array = [QSAroundMines getAroundMinesArrayByItem:itemInQueue graph:graph];
for (QSItem *itemInArray in array) {
//遍歷過 或 雷 或 打開了 則跳過
if (itemInArray.isTraveled == YES || itemInArray.isMine == YES || itemInArray.isOpened == YES){
continue;
}
//周邊雷數(shù)為0則加入隊(duì)列
if (itemInArray.arroundMineNumber == 0) {
itemInArray.opened = YES;
itemInArray.traveled = YES;
[queue insertValueAtTailOfQueue:itemInArray];
}
//周邊雷數(shù)不為0,不加入隊(duì)列,但設(shè)置為遍歷過,并打開
else{
itemInArray.opened = YES;
itemInArray.traveled = YES;
}
}//for
}//while
}
