模拟|UPC-自习课中国石油大学OJ|ACM

山再高，往上爬，总能登顶；
路再长，走下去，定能到达。
自习课题目描述

自习课就是划水课。你和同桌在玩井字棋，你先手。突然老师进来了。给定一个局面，问它是否有可能下的出来。若有可能，求出是否有赢家，若有，输出赢家。否则，输出是否平局，或者下一步是谁的回合。

输入

有多组数据，第一行给出数据组数 T。每组数据有 3 行，每行 3 个字符。若字符为”X”，表示这里你下过，若字符为”O”，表示这里同桌下过。若字符为”.”，表示这里没有人下过。

输出

每个数据输出一行。若不可能下的出来，输出Illegal Situation 若你赢了，输出X wins，若同桌赢了，输出O wins 若已经下完了，且平局，输出Draw 若下一步是你的回合，输出X's turn 若下一步是同桌的回合，输出O's turn

Sample Input

5 ... XX. ..O XOX XXO OXO .O. XO. .O. XOX OX. X.O XXX OOO ...

Sample Output

O's turn Draw Illegal Situation X wins Illegal Situation

Hint

对于前 60% 的数据，不存在三个”X”或”O”连成一线的情况；对于 100% 的数据，T≤100。

思路分析
这题考察的就是模拟的能力。打模拟的要诀就是思维缜密+沉住气
模拟的代码都会写，但是一写就wa，这就巨难受。本来这个我认为还OK的代码能过的，就是在比赛场上浮躁了，自己又推翻重写。
下面就详细分析一下我的思路过程。
这题不难，就是问你现在的井字棋走到这个地步了，让你判断以下几个复合什么情况
X先手
0.不可能出现这个情况
1.X该走了
2.O该走了
3.X 已经赢了
4.O 已经赢了
5.平局（没有胜负，都符合规则，已经X+O=9了）
仔细想想，如果当前没有可以连成线的方案，你完全可以根据棋子的数量来判断合法性，如果合法也很容易知道接下来谁走
方案是，先判断有无可成线的棋子
判断X的个数和O的个数
X一定不会比O少
X和O的差距不会大于1
如果满足这个条件OK，那么这就是没有成线且合理
如果X=O那么就说明该X走了
反之O走
如果上面没有给出结果，就说明有三点成线
如果说数量差的离谱，直接一寻找X和O的值的大小就可以了，如上步的方法。可以简单判断是否合法。
如果数量有可能性，且有连成线的，那么就得看看，你现在的Win是否合法（只有一人胜出）
这里就很迷人了。
首先相交的一定是同棋子。（可成的线路相交）而且一个棋子最多为5（X的）
那么一定是可行的。
那么你就寻找一下有没有是平行的可成线。
如果有判不合法
如果没有呢？是不是一定就是成立了呢？
不是的，想要成立的最后一个条件就是，我这个成立情形有没有可能出现。我们在前面只判断了数量差距的不可能性，但是如果我这一步的上一步就不可能实现呢？
比如X有3个O有3个，想X赢的前提是X有2个O有两个这是不可能的，想O赢的前天是X有3个O有两个，这也是不能的。所以，必须得满足这个条件，如果不能则一定不可。
此上已经表达了满足了所有可以成立的条件。
如果依然不能判对，那么这就是错的。
我把生成全部情况的样例代码奉上

#include #pragma GCC optimize(2) using namespace std; typedef long long ll; int cnt = 0; int x, y; char save[20][20]; void id(int t) { switch (t) { case 0:x = 0, y = 0; break; case 1:x = 0, y = 1; break; case 2:x = 0, y = 2; break; case 3:x = 1, y = 0; break; case 4:x = 1, y = 1; break; case 5:x = 1, y = 2; break; case 6:x = 2, y = 0; break; case 7:x = 2, y = 1; break; case 8:x = 2, y = 2; break; } } void dfs(int t) { if (t == 9) { cnt++; for (int i = 0; i < 3; i++)cout << save[i] << endl; return; } id(t); save[x][y] = '.'; dfs(t + 1); id(t); save[x][y] = 'O'; dfs(t + 1); id(t); save[x][y] = 'X'; dfs(t + 1); } int main() { freopen("C:\\Users\\hp\\Desktop\\find.txt", "w", stdout); //自由更改路径 dfs(0); cout << cnt << endl; //注意要把cnt的值自己手动放到顶端 fclose(stdout); }

大家可以吧自己和我的生成数据进行对比，一点点的进行调试。
好吧，接下来上代码 AC时间到

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4244) #define PI 3.141592653589793 #pragma GCC optimize(2) #define accelerate cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); #define EPS 1.0e-8 using namespace std; typedef long long ll; typedef unsigned long long ull; const ll ll_inf = 9223372036854775807; const int int_inf = 2147483647; const short short_inf = 32767; const char char_inf = 127; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } inline ll read() { ll c = getchar(), Nig = 1, x = 0; while (!isdigit(c) && c != '-')c = getchar(); if (c == '-')Nig = -1, c = getchar(); while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar(); return Nig * x; } inline void out(ll a) { if (a < 0)putchar('-'), a = -a; if (a >= 10)out(a / 10); putchar(a % 10 + '0'); } ll phi(ll n) { ll ans = n, mark = n; for (ll i = 2; i * i <= mark; i++) if (n % i == 0) { ans = ans * (i - 1) / i; while (n % i == 0)n /= i; } if (n > 1)ans = ans * (n - 1) / n; return ans; } ll qpow(ll x, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1)res = (res * x) % mod; x = (x * x) % mod; n >>= 1; } return res; } #define Floyd for(int k = 1; k <= n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++) #define read read() int Num_X, Num_O; char save[5][5]; short num() { Num_X = 0, Num_O = 0; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { if (save[i][j] == 'X')Num_X++; else if (save[i][j] == 'O')Num_O++; } if (Num_X < Num_O || Num_X - Num_O>1)return 0; if (Num_X + Num_O == 9)return 5; if (Num_X == Num_O)return 1; else return 2; } bool suc() { bool sw; for (int i = 0; i < 3; i++)//判断行方向，和列方向有没有成三的 { if (save[i][0] != '.' && save[i][0] == save[i][1] && save[i][0] == save[i][2]) return true; if (save[0][i] != '.' && save[0][i] == save[1][i] && save[0][i] == save[2][i]) return true; } if (save[1][1] != '.' && save[0][0] == save[1][1] && save[1][1] == save[2][2]) return 1; if (save[1][1] != '.' && save[2][0] == save[1][1] && save[1][1] == save[0][2]) return 1; return 0; } int judge() { if (!strcmp(save[0], "XOX") && !strcmp(save[2], "XOX") && !strcmp(save[1], "OXO"))return 1; //差重合 //先判断，如果说没有走到end，即x/y走下一个，且没有明显不合法。就返回3/4； if (!suc())return num(); //没有成功的 if (num() == 0)return 0; //数量不合法 //有成功的，且数量合法的。 //如果横成3，可以有列成三，和斜成三，且一定一样。如果列成3，可以有横成三，斜成3，且一定一样。 short xisr = 0, oisr = 0, xisc = 0, oisc = 0; for (int i = 0; i < 3; i++) { if (save[i][0] != '.' && save[i][0] == save[i][1] && save[i][0] == save[i][2]) if (save[i][0] == 'X')xisr++; else oisr++; if (save[0][i] != '.' && save[0][i] == save[1][i] && save[0][i] == save[2][i]) if (save[0][i] == 'X')xisc++; else oisc++; } if (xisr && oisr || xisc && oisc)return 0; //如果行列有多三 int x = Num_X, o = Num_O; if (save[1][1] != '.' && save[0][0] == save[1][1] && save[1][1] == save[2][2]) { if (save[1][1] == 'X') { if (x - o == 1)return 3; else return 0; } else if (o == x)return 4; } if (save[1][1] != '.' && save[0][2] == save[1][1] && save[1][1] == save[2][0]) { if (save[1][1] == 'X') { if (x - o == 1)return 3; else return 0; } else if (o == x)return 4; } if (xisr || oisr) { if (xisr) { if (x - o == 1)return 3; else return 0; } else if (o == x) return 4; } if (xisc || oisc) { if (xisc) { if (x - o == 1)return 3; else return 0; } else if (o == x)return 4; } return 0; } int main() { int T = read; while (T--) { for (int i = 0; i < 3; i++)scanf("%s", save[i]); int mark = judge(); switch (mark) { case 0:puts("Illegal Situation"); break; case 1:puts("X's turn"); break; case 2:puts("O's turn"); break; case 3:puts("X wins"); break; case 4:puts("O wins"); break; case 5:puts("Draw"); break; } } return 0; }

【模拟|UPC-自习课】如果有疑问敬请留言。
By-轮月