美文网首页Ios开发学习
iOS 广度优先搜索算法 实现扫雷自动‘翻牌’功能

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

作者: 七维树 | 来源:发表于2017-01-05 15:44 被阅读150次

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

相关文章

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

    这个算法自己在学习iOS开发做的一个扫雷游戏,并且已经上了AppStore ,但是之后一直在忙没顾得上优化,如果大...

  • 广度优先搜索算法(BFS)

    广度优先搜索算法(BFS) 标签(空格分隔): algorithm 1.广度优先搜索算法(Breadth Firs...

  • python 广度优先算法

    文章概述 广度优先搜索算法概述 广度优先搜索算法 广度优先算法是基于树或者图的,当然树也是一种特殊的图,因此我们先...

  • 搜索

    一、深度优先搜索 图深度优先遍历、深度优先搜索算法求有权图两点最短路径 二、广度优先搜索 图广度优先遍历、广度优先...

  • 【数据结构】广度优先搜索算法BFS

    对于广度优先遍历算法DFS可以参考前一篇文章【数据结构】深度优先搜索算法DFS 广度优先遍历 广度优先遍历(Bre...

  • 算法图解 (六)

    第六章 广度优先搜索 广度优先搜索算法 (英文: Breadth-First-Search, 缩写为BFS), 又...

  • 算法(三):图解广度优先搜索算法

    算法简介 广度优先搜索算法(Breadth First Search),又称为"宽度优先搜索"或"横向优先搜索",...

  • 最佳优先搜索算法(Best-First-Search)

    1、算法原理 最佳优先搜索算法是一种启发式搜索算法(Heuristic Algorithm),其基于广度优先搜索算...

  • 数据结构与算法--BFS&DFS

    “搜索”算法 深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构。 图上的搜索算法就是,在图中找出从一个...

  • Java广度/宽度(BFS)优先搜索实现

    最近复习了一下图的搜索算法,用Java实现一下练个手。广度优先算法,又叫宽度优先算法,Breadth-First ...

网友评论

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

    本文链接:https://www.haomeiwen.com/subject/gtszvttx.html