扫雷 (minesweeper)

题目描述

你需要编写一个扫雷交互器，获取地图信息，依次读入玩家操作并返回对应结果。

扫雷的局面是一个n×m的矩形，其中一些位置为地雷而另一些位置为空地，扫雷局面将以字符矩阵的形式输入。
将第i行第j列的位置记作(i,j)。特别地，令k为地雷的数量，保证有0<k<n×m 。

一开始玩家无法得知除了n,m,k之外的扫雷局面的任何信息。
你需要维护名为玩家地图的字符矩阵，初始时矩阵中所有元素为 _（下划线）。
玩家将进行q次操作，每次将选取一个位置(x,y)，并用以下三种方式之一点击：
（若游戏结束，你应该忽略游戏结束后的所有玩家操作，即判定这些操作为无效操作，反之即为有效操作）
1.左键点击：
若(x,y)已经被打开或玩家地图中这个位置为 P（P 表示旗子），则不进行任何操作；否则
若(x,y)为地雷，则游戏失败；否则
对(x,y)进行打开操作。
2.右键点击：
若(x,y)已经被打开，则不进行任何操作；否则
若玩家地图中位置(x,y)为 _，将其改为 P，
若玩家地图中位置(x,y)为 P，将其改为 ?，
若玩家地图中位置(x,y)为 ?，将其改为 _。
3.中键点击：
若(x,y)未被打开，则不进行任何操作；否则
若玩家地图中这个位置周围相邻的8个位置的 P 的个数不等于玩家地图中该位置的数值，则不进行任何操作；否则
对(x,y)周围相邻8个未被打开且在玩家地图中不是 P 的位置，如果存在至少一个位置是地雷，则游戏失败；否则
对这些位置进行打开操作。

打开操作：
·对位置(x,y)进行的打开操作按照如下方式进行：
·将(x,y)标记为被打开。
·在玩家地图中位置(x,y)改为c（0≤c≤8），表示这个位置周围相邻的8个位置的地雷数量。
·如果c=0，则对其周围相邻的8个未被打开且在玩家地图中不是 P 的位置进行打开操作。

这个操作是递归进行的，直到所有子操作都结束后，本次打开操作才算结束。

游戏结束，游戏结束有以下三种情况：
1.游戏失败：即上述规则中的情况，试图对为地雷的位置进行打开操作就会导致游戏失败。
2.游戏胜利：若某一次操作结束后，未被打开的位置个数恰好为k，则此次操作后游戏胜利。
3.退出游戏：若玩家操作结束，但上述两种情况均未出现，则视作玩家退出游戏。

在每一次操作后，你需要返回结果，具体规则如下：
·若此次操作为无效操作，返回 INVALID；否则
·若此次操作后游戏失败，返回 LOSE；否则
·先返回 RUNNING:，然后在同一行返回用中括号包含的，玩家地图中有更改的位置以及更改后的值，格式为 <x, y, val>；
·更改的位置按照x坐标为第一关键字从小到大，y坐标为第二关键字从小到大的顺序排序，相邻两个更改的位置用 , 隔开。
例如某一次操作后可能返回：RUNNING: [<2, 2, 2>, <2, 3, 1>, <3, 2, 1>, <3, 3, 0>]；
或 RUNNING: []；或 RUNNING: [<3, 3, ?>]。注意其中空格的位置。
·若此次操作后游戏胜利，再在新的一行返回 WIN。
·若此次操作后退出游戏，再在新的一行返回 QUIT。

输入

本题输入文件包含多组数据。
第一行一个正整数T表示数据组数，接下来每n+q-2行（意义见下）表示一组数据。
每组数据第一行两个正整数n,m分别表示扫雷局面的高度和宽度。
每组数据接下来n行，第i行一个长度为m的字符串，仅包含 _ 和 * 两种字符。
如果第j个字符为 *，则表示第 i行第j列为地雷，否则为空地。
每组数据接下来若干行，每行三个正整数op,x,y表示玩家的一次操作，具体操作见题目描述。
每组数据最后一行一个数0，表示玩家操作结束。令玩家操作次数为q。

输出

对于每组数据，输出若干行，每行表示一次操作的返回结果，若在某一次操作后游戏结束，请输出对应的结果。

相邻的两组数据之间使用一行 ==========（10 个 = 字符，不包含引号）隔开。

样例输入

5
3 3
__*
___
___
1 3 1
1 1 3
0
3 3
_*_
__*
___
1 3 1
1 1 3
2 1 2
2 2 3
3 2 2
1 1 2
2 2 1
3 3 3
0
3 3
***
___
***
1 2 2
0
3 3
___
_*_
___
1 2 2
1 1 1
0
3 3
___
__*
___
1 2 2
2 1 2
3 2 2
2 2 3
0

样例输出

RUNNING: [<1, 1, 0>, <1, 2, 1>, <2, 1, 0>, <2, 2, 1>, <2, 3, 1>, <3, 1, 0>, <3, 2, 0>, <3, 3, 0>]
WIN
INVALID
==========
RUNNING: [<2, 1, 1>, <2, 2, 2>, <3, 1, 0>, <3, 2, 1>]
RUNNING: [<1, 3, 2>]
RUNNING: [<1, 2, P>]
RUNNING: [<2, 3, P>]
RUNNING: [<1, 1, 1>, <3, 3, 1>]
WIN
INVALID
INVALID
INVALID
==========
RUNNING: [<2, 2, 6>]
QUIT
==========
LOSE
INVALID
==========
RUNNING: [<2, 2, 1>]
RUNNING: [<1, 2, P>]
LOSE
INVALID

提示

以下是对样例的五组数据的解释，每组数据从左到右依次描述了扫雷局面以及每一次有效操作后的玩家矩阵。
第一组数据：
__* | ___ | 01_
___ | ___ | 011
___ | ___ | 000
第二组数据：
_*_ | ___ | ___ | __2 | _P2 | _P2 | 1P2
__* | ___ | 12_ | 12_ | 12_ | 12P | 12P
___ | ___ | 01_ | 01_ | 01_ | 01_ | 011
第三组数据：
*** | ___ | ***
___ | ___ | _6_
*** | ___ | ***
第四组数据（玩家矩阵中不包含 x 字符，最后一个矩阵仅作说明用，不是真实的玩家矩阵）：
___ | ___ | ___
_*_ | ___ | _x_
___ | ___ | ___
第五组数据（玩家矩阵中不包含 x 字符，最后一个矩阵仅作说明用，不是真实的玩家矩阵）：
___ | ___ | ___ | _P_ | 0P1
__* | ___ | _1_ | _1_ | 01x
___ | ___ | ___ | ___ | 011

思路：一道超长的模拟题，题目里面把每一个过程还是说的很清楚的，都告诉了该怎么模拟。

记录几个我出错的点：

（1）无效操作。题目中说了游戏结束后玩家的操作才是无效操作，其余都是有效的，对于那些无需操作的，应该是输出RUNNING: []

（2）输出格式。题目中说了要注意空格，还是没注意（囧）

（3）在执行打开操作时，有可能一个符合条件的都没有，无法加进队列，导致队列为空，输出RUNNING: []

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=200010;
int n,m,tans;
char a[210][210];
bool f[210][210];
bool isLei[210][210];
int fx[9]={0,1,1,1,0,0,-1,-1,-1};
int fy[9]={0,1,0,-1,1,-1,1,0,-1};
struct Point{int xx,yy,val;
};
struct cmp{bool operator()(const Point&x,const Point&y){if (x.xx!=y.xx)return x.xx>y.xx;return x.yy>y.yy;}
};
void open(int x,int y,priority_queue<Point,vector<Point>,cmp>&q){f[x][y]=true;tans--;int c=0;int tx,ty;for (int i=1;i<=8;i++){          tx=x+fx[i];ty=y+fy[i];if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&isLei[tx][ty])c++;        }a[x][y]=c+'0';q.push({x,y,c});if (c==0){for (int i=1;i<=8;i++){tx=x+fx[i],ty=y+fy[i];if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&(!f[tx][ty])&&a[tx][ty]!='P')open(tx,ty,q);}}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>n>>m;int ans=0;//地雷的数量memset(isLei,false,sizeof(isLei)); for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){char c;cin>>c;if(c=='*'){ans++;isLei[i][j]=true;}a[i][j]='_';}}tans=n*m;memset(f,false,sizeof(f));bool ok=false;//是否已经退出游戏 int op,x,y;while(1){cin>>op;if (op==0){if (!ok)cout<<"QUIT\n";if (T!=0)cout<<"==========\n";break;}cin>>x>>y;if(ok){cout<<"INVALID\n";continue;} 
//          ____________________________if (op==1){if(f[x][y]||a[x][y]=='P'){cout<<"RUNNING: []\n";continue;}if(isLei[x][y]){cout<<"LOSE\n";ok=true;continue;}//打开操作priority_queue<Point,vector<Point>,cmp>q;open(x,y,q);cout<<"RUNNING: [";while(!q.empty()){auto t=q.top();q.pop();cout<<"<"<<t.xx<<", "<<t.yy<<", "<<t.val<<">";if (!q.empty())cout<<", ";   }cout<<"]\n";if (tans==ans){cout<<"WIN\n";ok=true;}}
//          _____________________________if(op==2){if (f[x][y]){cout<<"RUNNING: []\n";continue;}if(a[x][y]=='_')        a[x][y]='P';else if(a[x][y]=='P')   a[x][y]='?';else if(a[x][y]=='?')   a[x][y]='_';cout<<"RUNNING: [<"<<x<<", "<<y<<", "<<a[x][y]<<">]\n";}
//          ______________________________if (op==3){if (!f[x][y]){cout<<"RUNNING: []\n";continue; }int tx,ty;int tcnt=0,cnt=a[x][y]-'0';for (int i=1;i<=8;i++){tx=x+fx[i],ty=y+fy[i];if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]=='P')tcnt++;}if (tcnt!=cnt){cout<<"RUNNING: []\n";continue;}priority_queue<Point,vector<Point>,cmp>q;for (int i=1;i<=8;i++){tx=x+fx[i],ty=y+fy[i];if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]!='P'&&(!f[tx][ty])){if (isLei[tx][ty]){ok=true;break;}else{open(tx,ty,q);}}}if (ok){cout<<"LOSE\n";continue;}cout<<"RUNNING: [";while(!q.empty()){auto t=q.top();q.pop();cout<<"<"<<t.xx<<", "<<t.yy<<", "<<t.val<<">";if (!q.empty())cout<<", ";                   }cout<<"]\n";if (tans==ans){cout<<"WIN\n";ok=true;}}}}
}