第一遍用了队列来处理dsweep和连锁反应,最后一个例子过不了,后面改为为迭代调用。
//变量
const int N = 1010;
int n, m;
int numofde; //单次探索数量
int numofboom = 0, total_de = 0; //炸弹总数、已经探索的点数
int total_step = 0; //总步数
//数据存储
int mp[N][N]; //描述状态:未探明为-1, 被标注为-2, 扫描后显示周围炸弹数量
bool isboom[N][N]; //记录炸弹位置
struct node{} re[N * N]; //记录单次扫描过的节点,用于输出
功能函数:
int cnt_flag(int x, int y); //计算一个点相邻的flag数量
int cnt_boom(int x, int y); //计算一个点相邻的炸弹数量
int ms(int x, int y); //扫雷
void out_print(); //单次sweep/dsweep后输出
bool check(); //检查是否扫描完所有点
void game_over(int k); //k为: -1表示失败, 1表示成功, 2表示放弃
//调用sweep/dsweep后返回值不为0,则调用game_over(k), 游戏结束
调用接口(对应于各种输入情况):
void quit();
void flag(int x, int y);
int sweep(int x, int y);
int dsweep(int x, int y);
C++ 代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int numofde; //单次探索数量
int numofboom = 0, total_de = 0; //炸弹总数、已经探索的点数
int total_step = 0; //总步数
int mp[N][N]; //描述状态:未探明为-1, 被标注为-2, 扫描后显示周围炸弹数量
bool isboom[N][N]; //记录炸弹位置
struct node //记录单次扫描的各点,用于排序输出
{
int a, b;
bool operator <(const node &t)
{
if(a == t.a) return b < t.b;
return a < t.a;
}
}re[N * N];
int cnt_flag(int x, int y) //计算一个点相邻的flag数量
{
int cnt = 0;
for(int i = -1; i <= 1; i ++)
for(int j = -1; j <= 1; j ++)
{
if(!i && !j) continue;
int u = x + i, v = y + j;
if(u && u <= n && v && v <= m && mp[u][v] == -2)
cnt ++;
}
return cnt;
}
int cnt_boom(int x, int y) //计算一个点相邻的炸弹数量
{
int cnt = 0;
for(int i = -1; i <= 1; i ++)
for(int j = -1; j <= 1; j ++)
{
if(!i && !j) continue;
int u = x + i, v = y + j;
if(u && u <= n && v && v <= m && isboom[u][v])
cnt ++;
}
return cnt;
}
//k为, -1表示失败, 1表示成功, 2表示放弃
//调用sweep/dsweep后返回值不为0,则调用game_over(k), 游戏结束
void game_over(int k)
{
if(k == 1) printf("finish\n");
else if(k == -1) printf("game over\n");
else if(k == 2) printf("give up\n");
printf("total step %d\n", total_step);
}
int ms(int x, int y) //扫雷
{
if(isboom[x][y])
{
printf("boom\n");
game_over(-1);
return -1;
}
mp[x][y] = cnt_boom(x, y);
re[numofde].a = x; //记录当前点
re[numofde].b = y;
numofde ++;
if(!mp[x][y]) //连锁反应
for(int i = -1; i <= 1; i ++)
for(int j = -1; j <= 1; j ++)
{
if(!i && !j) continue;
int u = x + i, v = y + j;
if(u && u <= n && v && v <= m && mp[u][v] < 0)
if(ms(u, v) == -1) return -1;
}
return 0;
}
void out_print() //单次sweep/dsweep后输出
{
if(!numofde)
{
printf("no cell detected\n");
return;
}
sort(re, re + numofde);
printf("%d cell(s) detected\n", numofde);
for(int i = 0; i < numofde; i ++)
{
int x = re[i].a, y = re[i].b;
printf("%d %d %d\n", x, y, mp[x][y]);
}
}
bool check() //检查是否扫描完所有点
{
total_de += numofde;
if(total_de + numofboom == n * m) return true;
return false;
}
void quit()
{
game_over(2);
}
void flag(int x, int y) //Flag
{
if(mp[x][y] >= 0 ) printf("swept\n");
else if(mp[x][y] == -1)
{
mp[x][y] = -2;
printf("success\n");
}
else
{
mp[x][y] = -1;
printf("cancelled\n");
}
}
int sweep(int x, int y) //Sweep
{
numofde = 0;
if(mp[x][y] >= 0) printf("swept\n");
else if(mp[x][y] == -2) printf("flagged\n");
else
{
if(ms(x, y) == -1) return -1;
out_print();
if(check())
{
game_over(1);
return 1;
}
}
return 0;
}
int dsweep(int x, int y) //DSweep
{
numofde = 0;
if(mp[x][y] < 0) printf("not swept\n");
else if(mp[x][y] == 0 || mp[x][y] != cnt_flag(x, y)) printf("failed\n");
else
{
for(int i = -1; i <= 1; i ++) //扫描周围点
for(int j = -1; j <= 1; j ++)
{
int u = x + i, v = y + j;
if(u && u <= n && v && v <= m && mp[u][v] == -1)
if(ms(u, v) == -1) return -1;
}
out_print();
if(check())
{
game_over(1);
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
memset(mp, -1, sizeof mp);
for(int i = 1; i <= n; i ++)
{
char s[N];
scanf("%s", s);
for(int j = 1; j <= m; j ++)
if(s[j-1] == '*') isboom[i][j] = true, numofboom ++;
}
string op;
while(cin >> op)
{
if(op == "Quit") quit();
total_step ++;
int x, y;
cin >> x >> y;
//调用sweep/dsweep后返回值不为0,则调用game_over(k), 游戏结束
if(op == "Flag") flag(x, y);
if(op == "Sweep")
if(sweep(x, y)) break;
if(op == "DSweep")
if(dsweep(x, y)) break;
}
return 0;
}