时间过得真快，倏忽之间，毕业已近一年。
毕业答辩时做的项目有个游戏模块，扫雷游戏。当时也是想挑战一下自己，于是就着手构思怎么实现这个游戏。前前后后大概用了一周时间完成了扫雷的基本功能，如点击扫雷，长按标注地雷，难度选择等。但没有实现点击空白单元周围也翻过来的功能。后来在一次面试中，和一个技术总监谈到游戏的不足时，他提示到可以用递归遍历的方法找到点击的空白单元周围所有可以翻转单元的位置，才恍然大悟。
闲话少说，且看我的思路和实现过程
还是先上 Demo
#以下以10×10地图为例进行分析
定义
1）用数组mineMapArray（0 - 9）存储每个单元的状态，初始化全为0
0，表示单元周围没有地雷
1 - 8，表示单元周围有1 - 8个地雷
9，表示该单元是地雷单元的周围是指，当前单元的左上方、上方、右上方、右方、右下方、下方、左下方、左方的单元。一个单元周围最多有8个单元。
2）用数组minesArray（0 - 99）存储所有地雷的位置
3）用数组turnoverArray（0 - 99）存储点击空白单元时可翻转所有单元的位置
1、随机地雷的位置
1）先创建临时地图位置数组tmpMapArray（0 - 99），方便下一步随机_mineNums个地雷位置用
//1.创建临时地图位置数组，用于随机出地雷位置
NSMutableArray *tmpMapArray = [NSMutableArray array];//临时地图位置数组
for (int i = 0; i < _row * _column; i++) {
[tmpMapArray addObject:@(i)];
}
2）随机产生_mineNums个地雷并记录地雷位置到地图相应mineMapArray上
delIndex，临时地图数组tmpMapArray的删除的位置
addIndex，地雷地图数组minesArray上添加地雷的位置
//2.更新地图地雷位置和记录地雷位置
int delIndex;//随机地雷的位置
int addIndex;//地雷添加到地图的位置
for (int i = 0; i < _mineNums; i++) {
delIndex = arc4random() % tmpMapArray.count;
addIndex = [tmpMapArray[delIndex] intValue];
[self.mineMapArray replaceObjectAtIndex:addIndex withObject:@(9)];//更地图上地雷位置
[self.minesArray addObject:tmpMapArray[delIndex]];//添加地雷位置到存储所有地雷位置的数组
[tmpMapArray removeObjectAtIndex:delIndex];//删除临时随机的地雷位置
}
3）计算每个不是地雷的单元的周围地雷数量
一般情况下地雷的数量比较少，所以，首先我们可以遍历找到地雷单元，然后再遍历地雷周围的单元，再在mineMapArray数组相应位置上加1。
地雷的位置是
location，_row是行数，_column是列数，即一行单元的个数
所以，
左上 =location - _column - 1
上 =location - _column
右上 =location - _column + 1
右 =location + 1
右下 =location + _column + 1
下 =location + _column
左下 =location + _column - 1
左 =location - 1
注意：在遍历周围单元是要注意是否在边界位置
location / _column != 0判断当前单元是否在第一行
location % _column != 0判断当前单元是否在第一列
location / _column != _row - 1判断当前单元是否在最后一行
location % _column != _column - 1判断当前单元是否在最后一列左上单元，需要判断当前单元是否在第一行&&是否在第一列
上单元，需要判断当前单元是否在第一行
右上单元，需要判断当前单元是否在第一行&&是否在最后一列
右单元，需要判断当前单元是否在最后一列
右下单元，需要判断当前单元是否在最后一行&&最后一列
下单元，需要判断当前单元是否在最后一行
左下单元，需要判断当前单元是否在最后一行&&第一列
左单元，需要判断当前单元是否在第一列
//3.标记地雷周围数字
for (NSNumber *obj in self.minesArray) {//找到地雷周围位置，标记数值加1
NSInteger location = [obj integerValue];
NSInteger aroundLocation;//遍历地雷周围8个位置
//location / _column != 0 判断是否在第一行
//location % _column != 0 判断是否在第一列
//location / _column != _row - 1 判断是否在最后一行
//location % _column != _column - 1 判断是否在最后一列
//
aroundLocation = location - _column;//上
if (location / _column != 0) {
[self locationPlus:aroundLocation];
}
aroundLocation = location - _column + 1;//右上
if (location / _column && location % _column != _column - 1) {
[self locationPlus:aroundLocation];
}
aroundLocation = location + 1;//右
if (location % _column != _column - 1) {
[self locationPlus:aroundLocation];
}
aroundLocation = location + _column + 1;//右下
if (location % _column != _column - 1 && location / _column != _row - 1) {
[self locationPlus:aroundLocation];
}
aroundLocation = location + _column;//下
if (location / _column != _row - 1) {
[self locationPlus:aroundLocation];
}
aroundLocation = location + _column - 1;//左下
if (location / _column != _row - 1 && location % _column != 0) {
[self locationPlus:aroundLocation];
}
aroundLocation = location - 1;//左
if (location % _column != 0) {
[self locationPlus:aroundLocation];
}
aroundLocation = location - _column - 1;//左上
if (location / _column != 0 && location % _column != 0) {
[self locationPlus:aroundLocation];
}
}
- (void)locationPlus:(NSInteger)location {
NSInteger cellMineNums = [[self.mineMapArray objectAtIndex:location] integerValue];
if (cellMineNums != 9) {
cellMineNums++;
}
[self.mineMapArray replaceObjectAtIndex:location withObject:@(cellMineNums)];
}
2、初始化地图
代码：
/**
* 初始化地图
*/
- (void)setupMapView {
for (int i = 0; i < _row * _column; i++) {
UIButton *button = [UIButton buttonWithType:UIButtonTypeCustom];
button.tag = kTag + i;
//设置frame
CGRect screenBounds = [UIScreen mainScreen].bounds;
CGFloat buttonW = (screenBounds.size.width - kBorderX * 2 - (_column - 1) * kGap) / _column;
CGFloat buttonH = buttonW;
CGFloat buttonX = (i % _column) * (buttonW + kGap) + kBorderX;
CGFloat buttonY = (i / _column) * (buttonH + kGap) + kBorderX;
button.frame = CGRectMake(buttonX, buttonY, buttonW, buttonH);
button.backgroundColor = [UIColor grayColor];
[button setBackgroundImage:[UIImage imageNamed:[NSString stringWithFormat:@"selected_%@", self.mineMapArray[i]]] forState:UIControlStateSelected];
[button setBackgroundImage:[UIImage imageNamed:@"selected_bg"] forState:UIControlStateNormal];
[button addTarget:self action:@selector(cellButtonSelect:) forControlEvents:UIControlEventTouchUpInside];
UILongPressGestureRecognizer *longPress = [[UILongPressGestureRecognizer alloc] initWithTarget:self action:@selector(markMine:)];
[button addGestureRecognizer:longPress];
[self.bgView addSubview:button];
}
}
随机地雷位置数组：
[0, 0, 0, 1, 9, 1, 0, 0, 1, 1,
0, 0, 0, 1, 1, 1, 1, 1, 2, 9,
0, 0, 0, 0, 0, 0, 1, 9, 4, 3,
0, 0, 0, 1, 2, 3, 3, 3, 9, 9,
0, 1, 1, 2, 9, 9, 9, 2, 2, 2,
0, 2, 9, 4, 4, 4, 3, 1, 0, 0,
0, 2, 9, 9, 2, 9, 2, 1, 1, 0,
0, 1, 2, 2, 2, 1, 2, 9, 1, 0,
1, 1, 1, 1, 1, 0, 1, 1, 1, 0,
9, 1, 1, 9, 1, 0, 0, 0, 0, 0]
地雷位置效果图：
3、扫雷逻辑
- 点击数字单元，数字单元翻过来
- 点击地雷单元，所有单元翻过来，游戏结束
- 点击空白单元，找出其周围“可翻转的单元”，并翻转过来
“可翻转的单元”是指，如下图，当点击绿色区域内任意空白单元时绿色区域全部翻转过来
下面是当点击黄点位置空白单元时，找到其周围可翻转的单元的思路和算法
思路：
① 如果当前单元是空白单元，先把这个单元存到turnoverArray;
② 再依次判断这个单元的上、右上、右、右下、下、左下、左、左上单元
③ 如果判断的单元是空白单元，则把判断的单元作为当前空白单元回到①;如果判断的单元是数字单元，则回到②依次进行判断；
核心算法：
- (void)findAllTurnover:(NSInteger)location {
if (![self.turnoverArray containsObject:@(location)]) {//如果turnoverArray不包含这个单元，存进去
[self.turnoverArray addObject:@(location)];
}
if ([self.mineMapArray[location] integerValue] != 0) {//如果当前单元不是空白单元则，回到上一层继续寻找下一个位置
return;
}
NSInteger aroundLocation;
aroundLocation = location - _column - 1;//左上
if (location / _column != 0 && location % _column != 0) {
[self addTurnover:aroundLocation];
}
aroundLocation = location - _column;//上
if (location / _column != 0) {
[self addTurnover:aroundLocation];
}
aroundLocation = location - _column + 1;//右上
if (location / _column && location % _column != _column - 1) {
[self addTurnover:aroundLocation];
}
aroundLocation = location + 1;//右
if (location % _column != _column - 1) {
[self addTurnover:aroundLocation];
}
aroundLocation = location + _column + 1;//右下
if (location % _column != _column - 1 && location / _column != _column - 1) {
[self addTurnover:aroundLocation];
}
aroundLocation = location + _column;//下
if (location / _column != _column - 1) {
[self addTurnover:aroundLocation];
}
aroundLocation = location + _column - 1;//左下
if (location / _column != _column - 1 && location % _column != 0) {
[self addTurnover:aroundLocation];
}
aroundLocation = location - 1;//左
if (location % _column != 0) {
[self addTurnover:aroundLocation];
}
}
- (void)addTurnover:(NSInteger)location {
if ([self.turnoverArray containsObject:@(location)]) {//如果已经包含这个单元return
return;
}
[self.turnoverArray addObject:@(location)];
[self findAllTurnover:location];
}
4、颇多不足，望各位不吝赐教
- 有些细节没有说明白
- 用递归遍历寻找空白单元周围可翻转单元时，时间复杂度太大。
