1 条题解
-
0
#include <set> #include <map> #include <cmath> #include <cstdio> #include <vector> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define LOCAL const int MAXL = 20; const long long MOD = 1000000007; const int MAXK = 10000 + 10; const int MAXN = 35000 + 10; const int MAXM = 35; const int INF = 0x7fffffff; using namespace std; char str[10][10]; int tot, X, Y;//代表棋子的数量 void init(){ tot = 0; for (int i = 1; i <= 4; i++){ scanf("%s", str[i] + 1); for (int j = 1; j <= 4; j++) if (str[i][j] != '.') tot++; } /*for (int i = 1; i <= 4; i++){ for (int j = 1; j <= 4; j++) printf("%c", str[i][j]); printf("\n"); }*/ } //判断是否达成胜利条件 bool check(int x, int y){ int num = 0;//判断棋子的个数 for (int i = 1;i <= 4; i++){ //注意不要全部判断了 if (str[x][i] == 'o') num++; else if (str[x][i] == 'x') num--; } if (num == 4 || num == -4) return 1; num = 0; for (int i = 1; i <= 4; i++){ if (str[i][y] == 'o') num++; else if (str[i][y] == 'x') num--; } if (num == 4 || num == -4) return 1; num = 0; //判断主对角线 for (int i = 1; i <= 4; i++){ if (str[i][i] == 'o') num++; else if (str[i][i] == 'x') num--; } if (num == 4 || num == -4) return 1; num = 0; for (int i = 1; i <= 4; i++){ if (str[i][4 - i + 1] == 'o') num++; else if (str[i][4 - i + 1] == 'x') num--; } if (num == 4 || num == -4) return 1; return 0; } int MaxSearch(int x, int y, int alpha); int MinSearch(int x, int y, int beta); int MaxSearch(int x, int y, int alpha){ int Ans = -INF; //最大获益 if (check(x, y)) return Ans; if (tot == 16) return 0; for (int i = 1; i <= 4; i++) for (int j = 1; j <= 4; j++){ if (str[i][j] != '.') continue; str[i][j] = 'x';tot++; int tmp = MinSearch(i, j, Ans); str[i][j] = '.';tot--; Ans = max(Ans, tmp); if (Ans >= alpha) return Ans; } return Ans; } int MinSearch(int x, int y, int beta){ int Ans = INF; //最小损失 if (check(x, y)) return Ans; if (tot == 16) return 0;//平局 for (int i = 1; i <= 4; i++) for (int j = 1; j <= 4; j++){ if (str[i][j] != '.') continue; str[i][j] = 'o'; tot++; int tmp = MaxSearch(i, j, Ans); str[i][j] = '.'; tot--; Ans = min(Ans , tmp); if (Ans <= beta) return Ans; } return Ans; } bool dfs(){ int beta = -INF; for (int i = 1; i <= 4; i++) for (int j = 1; j <= 4; j++){ if (str[i][j] != '.') continue; str[i][j] = 'x'; tot++; int tmp = MinSearch(i, j, beta); str[i][j] = '.'; tot--; beta = max(beta, tmp); if (beta == INF){ X = i;Y = j; return 1; } } return 0; } int main () { char ch[2]; while (scanf("%s", ch)!= EOF && ch[0] != '$'){ init(); if (dfs()) printf("(%d,%d)\n", X - 1, Y - 1);//代表终点坐标 else printf("#####\n"); } return 0; }
- 1
信息
- ID
- 569
- 时间
- 3000ms
- 内存
- 32MiB
- 难度
- 6
- 标签
- 递交数
- 12
- 已通过
- 1
- 上传者