超级井字棋
超级井字棋
整合 2024.8.24 某中学部分选手 AI。
相关题目
T503699 超级井字棋
规则说明
给出一个由九个井字棋盘组成的方形棋盘，对弈规则简单来说就是井字棋套井字棋，没玩过该棋的请自行琢磨具体游戏规则。
Code
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
typedef pair<int, int> pii;
namespace WZA {
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fir first
#define sec second
#define n 9
// board 0 1 -1
vector<pr>sel;
bool full[4][4];
mt19937 rd(1919810);
pr get_st(int x, int y) {
pr ans;
ans = {x * 3, y * 3};
return ans;
}
pr get_g(int x, int y) {
return {x / 3, y / 3};
}
void upd(int x, int y, const vector<vector<int>> &tmp) {
int cnt = 0;
rep(i, 0, 2)
rep(j, 0, 2)
cnt += tmp[3 * x + i][3 * y + j] == 0;
if (cnt == 0) {
full[x][y] = 1;
return;
}
rep(i, 0, 2) {
cnt = 0;
rep(j, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (abs(cnt) == 3) {
full[x][y] = 1;
return;
}
}
rep(j, 0, 2) {
cnt = 0;
rep(i, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (abs(cnt) == 3) {
full[x][y] = 1;
return;
}
} cnt = 0;
rep(i, 0, 2)
cnt += tmp[3 * x + i][3 * y + i];
if (abs(cnt) == 3) {
full[x][y] = 1;
return;
}
cnt = 0;
rep(i, 0, 2) //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + 2 - i];
if (abs(cnt) == 3) {
full[x][y] = 1;
return;
}
}
pr step(pr g, const vector<vector<int>> &tmp) {
sel.clear();
rep(i, 0, 2) {
rep(j, 0, 2) {
upd(i, j, tmp);
}
}
if (g.fir < 0) {
// cout<<">0\n";
rep(i, 0, 8) {
rep(j, 0, 8) {
sel.push_back({i, j});
}
}
shuffle(sel.begin(), sel.end(), rd);
rep(i, 0, 2) {
rep(j, 0, 2) {
if (full[i][j])continue;
pr g = {i, j};
rep(i, 0, 2) { //姣忚鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(j, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == 2) {
rep(j, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
rep(j, 0, 2) { //姣忓垪鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == 2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
int cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, 2) { //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + i];
}
if (cnt == 2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + i] == 0) {
return {3 * x + i, 3 * y + i};
}
}
}
cnt = 0;
rep(i, 0, 2) { //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + 2 - i];
}
if (cnt == 2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + 2 - i] == 0) {
return {3 * x + i, 3 * y + 2 - i};
}
}
}
//-2
rep(i, 0, 2) { //姣忚鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(j, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == -2) {
rep(j, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
rep(j, 0, 2) { //姣忓垪鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == -2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, -2) //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + i];
if (cnt == -2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + i] == 0) {
return {3 * x + i, 3 * y + i};
}
}
}
cnt = 0;
rep(i, 0, 2) { //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + 2 - i];
}
if (cnt == -2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + 2 - i] == 0) {
return {3 * x + i, 3 * y + 2 - i};
}
}
}
}
}
for (pr x : sel) {
if (tmp[x.fir][x.sec] == 0 && !full[x.fir / 3][x.sec / 3]) {
// cout<<x.fir<<' '<<x.sec<<"\n";
return x;
}
}
return {0, 0};
}
rep(i, 0, 2) { //姣忚鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(j, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == 2) {
rep(j, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
rep(j, 0, 2) { //姣忓垪鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == 2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
int cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, 2) //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + i];
if (cnt == 2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + i] == 0) {
return {3 * x + i, 3 * y + i};
}
}
} cnt = 0;
rep(i, 0, 2) //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + 2 - i];
if (cnt == 2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + 2 - i] == 0) {
return {3 * x + i, 3 * y + 2 - i};
}
}
}//-2
rep(i, 0, 2) { //姣忚鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(j, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == -2) {
rep(j, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
rep(j, 0, 2) { //姣忓垪鏄惁2杩?
int cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, 2) {
cnt += tmp[3 * x + i][3 * y + j];
}
if (cnt == -2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + j] == 0) {
return {3 * x + i, 3 * y + j};
}
}
}
}
cnt = 0, x = g.fir, y = g.sec;
rep(i, 0, -2) //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + i];
if (cnt == -2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + i] == 0) {
return {3 * x + i, 3 * y + i};
}
}
}
cnt = 0;
rep(i, 0, 2) //鍒ゆ柇瀵硅绾?
cnt += tmp[3 * x + i][3 * y + 2 - i];
if (cnt == -2) {
rep(i, 0, 2) {
if (tmp[3 * x + i][3 * y + 2 - i] == 0) {
return {3 * x + i, 3 * y + 2 - i};
}
}
}
rep(i, 0, 2)
rep(j, 0, 2)
sel.push_back({i, j});
shuffle(sel.begin(), sel.end(), rd);
for (pr x : sel) {
if (tmp[3 * g.fir + x.fir][3 * g.sec + x.sec] == 0) {
return {3 * g.fir + x.fir, 3 * g.sec + x.sec};
}
}
return {0, 0};
}
#undef rep
#undef per
#undef pr
};
namespace HYH {
//24/08/24 15:44
//胡轶恒
// board 0 1 -1
// id(0 -> 2, 0 -> 2) 表示当前要下的格子的坐标，(-1, -1)表示可以任意下
// 坐标从 0 开始
// 所有代码写在 namespace 里，step可以看做主函数
mt19937 rd(time(NULL));
pair<int, int> step(pair<int, int> id, const std::vector<std::vector<int>> &board) {
//乱搞
if (id.first == -1 && id.second == -1) {
/*for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
if(board[i][j]==0) return make_pair(i,j);
}
}*/int i, j;
while (1) {
i = rd() % 9;
j = (rd() + 2) % 9;
if (board[i][j] == 0) {
return make_pair(i, j);
}
}
}
//处理坐标
int x, y, t0, t1;
x = 3 * id.first + 1;
y = 3 * id.second + 1;
//占领大格
if (board[x - 1][y - 1] != -1 && board[x - 1][y] != -1 && board[x - 1][y] != -1) { //(-1,-1),(-1,0),(-1,1)
int cnt = 0, t2;
if (board[x - 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x - 1][y] == 0) ++cnt, t2 = 0;
if (board[x - 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x - 1][y + t2] == 0) {
return make_pair(x - 1, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x][y - 1] != -1 && board[x][y] != -1 && board[x][y] != -1) { //(0,-1),(0,0),(0,1)
int cnt = 0, t2;
if (board[x][y - 1] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x][y + t2] == 0) {
return make_pair(x, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x + 1][y - 1] != -1 && board[x + 1][y] != -1 && board[x + 1][y] != -1) { //(1,-1),(1,0),(1,1)
int cnt = 0, t2;
if (board[x + 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x + 1][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + 1][y + t2] == 0) {
return make_pair(x + 1, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y - 1] != -1 && board[x][y - 1] != -1 && board[x + 1][y - 1] != -1) { //(-1,-1),(0,-1),(1,-1)
int cnt = 0, t2;
if (board[x - 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x][y - 1] == 0) ++cnt, t2 = 0;
if (board[x + 1][y - 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y - 1] == 0) {
return make_pair(x + t2, y - 1);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y] != -1 && board[x][y] != -1 && board[x + 1][y] != -1) { //(-1,0),(0,0),(1,0)
int cnt = 0, t2;
if (board[x - 1][y] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y] == 0) {
return make_pair(x + t2, y);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y + 1] != -1 && board[x][y + 1] != -1 && board[x + 1][y + 1] != -1) { //(-1,1),(0,1),(1,1)
int cnt = 0, t2;
if (board[x - 1][y + 1] == 0) ++cnt, t2 = -1;
if (board[x][y + 1] == 0) ++cnt, t2 = 0;
if (board[x + 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y + 1] == 0) {
return make_pair(x + t2, y + 1);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y - 1] != -1 && board[x][y] != -1 && board[x + 1][y + 1] != -1) { //(-1,-1),(0,0),(1,1)
int cnt = 0, t2;
if (board[x - 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y + t2] == 0) {
return make_pair(x + t2, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y + 1] != -1 && board[x][y] != -1 && board[x + 1][y - 1] != -1) { //(-1,1),(0,0),(1,-1)
int cnt = 0, t2;
if (board[x - 1][y + 1] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y - 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y - t2] == 0) {
return make_pair(x + t2, y - t2);
}//else if(cnt==1) t1=;
}
//防止占领
if (board[x - 1][y - 1] != 1 && board[x - 1][y] != 1 && board[x - 1][y] != 1) { //(-1,-1),(-1,0),(-1,1)
int cnt = 0, t2;
if (board[x - 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x - 1][y] == 0) ++cnt, t2 = 0;
if (board[x - 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x - 1][y + t2] == 0) {
return make_pair(x - 1, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x][y - 1] != 1 && board[x][y] != 1 && board[x][y] != 1) { //(0,-1),(0,0),(0,1)
int cnt = 0, t2;
if (board[x][y - 1] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x][y + t2] == 0) {
return make_pair(x, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x + 1][y - 1] != 1 && board[x + 1][y] != 1 && board[x + 1][y] != 1) { //(1,-1),(1,0),(1,1)
int cnt = 0, t2;
if (board[x + 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x + 1][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + 1][y + t2] == 0) {
return make_pair(x + 1, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y - 1] != 1 && board[x][y - 1] != 1 && board[x + 1][y - 1] != 1) { //(-1,-1),(0,-1),(1,-1)
int cnt = 0, t2;
if (board[x - 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x][y - 1] == 0) ++cnt, t2 = 0;
if (board[x + 1][y - 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y - 1] == 0) {
return make_pair(x + t2, y - 1);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y] != 1 && board[x][y] != 1 && board[x + 1][y] != 1) { //(-1,0),(0,0),(1,0)
int cnt = 0, t2;
if (board[x - 1][y] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y] == 0) {
return make_pair(x + t2, y);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y + 1] != 1 && board[x][y + 1] != 1 && board[x + 1][y + 1] != 1) { //(-1,1),(0,1),(1,1)
int cnt = 0, t2;
if (board[x - 1][y + 1] == 0) ++cnt, t2 = -1;
if (board[x][y + 1] == 0) ++cnt, t2 = 0;
if (board[x + 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y + 1] == 0) {
return make_pair(x + t2, y + 1);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y - 1] != 1 && board[x][y] != 1 && board[x + 1][y + 1] != 1) { //(-1,-1),(0,0),(1,1)
int cnt = 0, t2;
if (board[x - 1][y - 1] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y + 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y + t2] == 0) {
return make_pair(x + t2, y + t2);
}//else if(cnt==1) t1=;
}
if (board[x - 1][y + 1] != 1 && board[x][y] != 1 && board[x + 1][y - 1] != 1) { //(-1,1),(0,0),(1,-1)
int cnt = 0, t2;
if (board[x - 1][y + 1] == 0) ++cnt, t2 = -1;
if (board[x][y] == 0) ++cnt, t2 = 0;
if (board[x + 1][y - 1] == 0) ++cnt, t2 = 1;
if (cnt == 1 && board[x + t2][y - t2] == 0) {
return make_pair(x + t2, y - t2);
}//else if(cnt==1) t1=;
}
//乱搞
/*for(int i=x-1;i<=x+1;++i){
for(int j=y-1;j<=y+1;++j){
if(board[i][j]==0) return make_pair(i,j);
}
}*/int i, j;
while (1) {
i = rd() % 3;
j = (rd() + 4) % 3;
if (board[x + i - 1][y + j - 1] == 0) {
return make_pair(x + i - 1, y + j - 1);
}
}
}
};
namespace FRZ {
//方睿喆
// board 0 1 -1
// id(0 -> 2, 0 -> 2) 表示当前要下的格子的坐标，(-1, -1)表示可以任意下
// 坐标从 0 开始
// 所有代码写在 namespace 里，step可以看做主函数
int a[20][20] = {{1, 1, 1, 2, 2, 2, 3, 3, 3}, {1, 1, 1, 2, 2, 2, 3, 3, 3}, {1, 1, 1, 2, 2, 2, 3, 3, 3}, {4, 4, 4, 5, 5, 5, 6, 6, 6}, {4, 4, 4, 5, 5, 5, 6, 6, 6}, {4, 4, 4, 5, 5, 5, 6, 6, 6}, {7, 7, 7, 8, 8, 8, 9, 9, 9}, {7, 7, 7, 8, 8, 8, 9, 9, 9}, {7, 7, 7, 8, 8, 8, 9, 9, 9}};
bool check1(const std::vector<std::vector<int>> &board, int x, int y) { //判断自己是否能赢
if (a[x][y] == a[x + 1][y] && a[x][y] == a[x + 2][y] && board[x + 1][y] == 1 && board[x + 2][y] == 1) return 1;
if (a[x][y] == a[x + 1][y + 1] && a[x][y] == a[x + 2][y + 2] && board[x + 1][y + 1] == 1 && board[x + 2][y + 2] == 1) return 1;
if (x >= 2 && y >= 2 && a[x][y] == a[x - 1][y - 1] && a[x][y] == a[x - 2][y - 2] && board[x - 1][y - 1] == 1 && board[x - 2][y - 2] == 1) return 1;
if (x >= 2 && a[x][y] == a[x - 1][y + 1] && a[x][y] == a[x - 2][y + 2] && board[x - 1][y + 1] == 1 && board[x - 2][y + 2] == 1) return 1;
if (y >= 2 && a[x][y] == a[x + 1][y - 1] && a[x][y] == a[x + 2][y - 2] && board[x + 1][y - 1] == 1 && board[x + 2][y - 2] == 1) return 1;
if (x >= 1 && y >= 1 && a[x][y] == a[x + 1][y + 1] && a[x][y] == a[x - 1][y - 1] && board[x + 1][y + 1] == 1 && board[x - 1][y - 1] == 1) return 1;
if (x >= 1 && y >= 1 && a[x][y] == a[x + 1][y - 1] && a[x][y] == a[x - 1][y + 1] && board[x - 1][y + 1] == 1 && board[x + 1][y - 1] == 1) return 1;
if (x >= 2 && a[x][y] == a[x - 1][y] && a[x][y] == a[x - 2][y] && board[x - 1][y] == 1 && board[x - 2][y] == 1) return 1;
if (y >= 2 && a[x][y] == a[x][y - 1] && a[x][y] == a[x][y - 2] && board[x][y - 1] == 1 && board[x][y - 2] == 1) return 1;
if (a[x][y] == a[x][y + 1] && a[x][y] == a[x][y + 2] && board[x][y + 1] == 1 && board[x][y + 2] == 1) return 1;
if (x >= 1 && a[x][y] == a[x + 1][y] && a[x][y] == a[x - 1][y] && board[x + 1][y] == 1 && board[x - 1][y] == 1) return 1;
if (y >= 1 && a[x][y] == a[x][y + 1] && a[x][y] == a[x][y - 1] && board[x][y + 1] == 1 && board[x][y - 1] == 1) return 1;
return 0;
}
bool check2(const std::vector<std::vector<int>> &board, int x, int y) { //判断敌人是否能赢
if (a[x][y] == a[x + 1][y] && a[x][y] == a[x + 2][y] && board[x + 1][y] == -1 && board[x + 2][y] == -1) return 1;
if (a[x][y] == a[x + 1][y + 1] && a[x][y] == a[x + 2][y + 2] && board[x + 1][y + 1] == -1 && board[x + 2][y + 2] == -1) return 1;
if (x >= 2 && y >= 2 && a[x][y] == a[x - 1][y - 1] && a[x][y] == a[x - 2][y - 2] && board[x - 1][y - 1] == -1 && board[x - 2][y - 2] == -1) return 1;
if (x >= 2 && a[x][y] == a[x - 1][y + 1] && a[x][y] == a[x - 2][y + 2] && board[x - 1][y + 1] == -1 && board[x - 2][y + 2] == -1) return 1;
if (y >= 2 && a[x][y] == a[x + 1][y - 1] && a[x][y] == a[x + 2][y - 2] && board[x + 1][y - 1] == -1 && board[x + 2][y - 2] == -1) return 1;
if (x >= 1 && y >= 1 && a[x][y] == a[x + 1][y + 1] && a[x][y] == a[x - 1][y - 1] && board[x + 1][y + 1] == -1 && board[x - 1][y - 1] == -1) return 1;
if (x >= 1 && y >= 1 && a[x][y] == a[x + 1][y - 1] && a[x][y] == a[x - 1][y + 1] && board[x - 1][y + 1] == -1 && board[x + 1][y - 1] == -1) return 1;
if (x >= 2 && a[x][y] == a[x - 1][y] && a[x][y] == a[x - 2][y] && board[x - 1][y] == -1 && board[x - 2][y] == -1) return 1;
if (y >= 2 && a[x][y] == a[x][y - 1] && a[x][y] == a[x][y - 2] && board[x][y - 1] == -1 && board[x][y - 2] == -1) return 1;
if (a[x][y] == a[x][y + 1] && a[x][y] == a[x][y + 2] && board[x][y + 1] == -1 && board[x][y + 2] == -1) return 1;
if (x >= 1 && a[x][y] == a[x + 1][y] && a[x][y] == a[x - 1][y] && board[x + 1][y] == -1 && board[x - 1][y] == -1) return 1;
if (y >= 1 && a[x][y] == a[x][y + 1] && a[x][y] == a[x][y - 1] && board[x][y + 1] == -1 && board[x][y - 1] == -1) return 1;
return 0;
}
bool check3(const std::vector<std::vector<int>> &board, int x, int y) { //下这步敌方是否能连起来
pair<int, int> ip;
ip.first = x / 3;
ip.second = y / 3;
for (int i = ip.first * 3; i < ip.first * 3 + 3; i++) {
for (int j = ip.second * 3; j < ip.second * 3 + 3; j++) {
if (board[i][j] != 0) continue;
if (check2(board, i, j)) return 1;
}
}
return 0;
}
bool check4(const std::vector<std::vector<int>> &board, int x, int y) { //下这步敌方是否能随便走
pair<int, int> ip;
ip.first = x / 3;
ip.second = y / 3;
int flag = 1;
for (int i = ip.first * 3; i < ip.first * 3 + 3; i++)
for (int j = ip.second * 3; j < ip.second * 3 + 3; j++)
if (board[i][j] == 0) flag = 0;
return flag;
}
pair<int, int> step(pair<int, int> id, const std::vector<std::vector<int>> &board) {
if (id.first == -1 && id.second == -1) {
int val[20][20] = {0};
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != 0) continue;
if (check1(board, i, j)) val[i][j] += 4;
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != 0) continue;
if (check2(board, i, j)) val[i][j] += 2;
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != 0) continue;
if (check3(board, i, j)) val[i][j] -= 3;
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != 0) continue;
if (check4(board, i, j)) val[i][j]--;
}
}
int maxn = -1e3;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (val[i][j] > maxn && board[i][j] == 0) maxn = val[i][j];
pair<int, int> can[90];
int tot = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (val[i][j] == maxn && board[i][j] == 0) {
tot++;
can[tot] = {i, j};
}
}
}
return can[max(tot - 1, 1)];
} else {
int val[20][20] = {0};
for (int i = id.first * 3; i < id.first * 3 + 3; i++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j++) {
if (board[i][j] != 0) continue;
if (check1(board, i, j)) val[i][j] += 4;
}
}
for (int i = id.first * 3; i < id.first * 3 + 3; i++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j++) {
if (board[i][j] != 0) continue;
if (check2(board, i, j)) val[i][j] += 2;
}
}
for (int i = id.first * 3; i < id.first * 3 + 3; i++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j++) {
if (board[i][j] != 0) continue;
if (check3(board, i, j)) val[i][j] -= 3;
}
}
for (int i = id.first * 3; i < id.first * 3 + 3; i++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j++) {
if (board[i][j] != 0) continue;
if (check4(board, i, j)) val[i][j]--;
}
}
int maxn = -1e3;
for (int i = id.first * 3; i < id.first * 3 + 3; i++)
for (int j = id.second * 3; j < id.second * 3 + 3; j++)
if (val[i][j] >= maxn && board[i][j] == 0) maxn = val[i][j];
pair<int, int> can[90];
int tot = 0;
for (int i = id.first * 3; i < id.first * 3 + 3; i++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j++) {
if (val[i][j] == maxn && board[i][j] == 0) {
tot++;
can[tot] = {i, j};
}
}
}
return can[max(tot - 1, 1)];
}
}
};
namespace WYR {
const int N = 1e6;
int c = 0;
pair<int, int> a[N];
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
memset(a, 0 , sizeof(a));
c = 0;
struct random {
random() {
srand(time(0));
}
} srandsetter;
mt19937 rnd(rand());
for (int x = 0; x <= 8; x ++) {
for (int y = 0; y <= 8; y ++) {
int g = (x / 3) * 3 , h = (y / 3) * 3;
if (((x / 3 == id.first && y / 3 == id.second) || (id.first == -1 && id.second == -1))) {
for (int i = 0; i <= 2; i ++) {
int js = 0, bj1 = -1, bj2 = -1;
int f = board[i + g][i + h];
if (f == 1) {
js ++;
}
if (f == 0) {
bj1 = i + g;
bj2 = i + h;
}
if (f == -1) {
js = -1e9;
bj1 = -1;
bj2 = -1;
}
if (js == 2 && bj1 != -1 && bj2 != -1) {
for (int k = 0; k <= 81; k++) a[++c] = make_pair(bj1, bj2);
}
}
for (int i = 0; i <= 2; i ++) {
int js = 0, bj1 = -1, bj2 = -1;
int f = board[i + g][(2 - i) + h];
if (f == 1) {
js ++;
}
if (f == 0) {
bj1 = i + g;
bj2 = (2 - i) + h;
}
if (f == -1) {
js = -1e9;
bj1 = -1;
bj2 = -1;
}
if (js == 2 && bj1 != -1 && bj2 != -1) {
for (int k = 0; k <= 81; k++) a[++c] = make_pair(bj1, bj2);
}
}
for (int i = 0; i <= 2; i ++) {
int js = 0, bj1 = -1, bj2 = -1;
for (int j = 0; j <= 2; j ++) {
int f = board[i + g][j + h];
if (f == 1) {
js ++;
}
if (f == 0) {
bj1 = i + g;
bj2 = j + h;
}
if (f == -1) {
js = -1e9;
bj1 = -1;
bj2 = -1;
}
}
if (js == 2 && bj1 != -1 && bj2 != -1) {
for (int k = 0; k <= 81; k++) a[++c] = make_pair(bj1, bj2);
}
}
for (int j = 0; j <= 2; j ++) {
int js = 0, bj1 = -1, bj2 = -1;
for (int i = 0; i <= 2; i ++) {
int f = board[i + g][j + h];
if (f == 1) {
js ++;
}
if (f == 0) {
bj1 = i + g;
bj2 = j + h;
}
if (f == -1) {
js = -1e9;
bj1 = -1;
bj2 = -1;
}
}
if (js == 2 && bj1 != -1 && bj2 != -1) {
for (int k = 0; k <= 81; k++) a[++c] = make_pair(bj1, bj2);
}
}
}
if (board[x][y] == 0 && ((x / 3 == id.first && y / 3 == id.second) || (id.first == -1 && id.second == -1))) {
a[++c] = make_pair(x, y);
}
}
}
return a[rnd() % c + 1];
}
}
namespace HBY {
//hby
mt19937 rd(time(NULL));
bool rule(pair<int, int> id, int x, int y) {
if (x < id.first * 3 || y < id.second * 3 || x >= id.first * 3 + 3 || y >= id.second * 3 + 3)return 0;
return 1;
}
bool check2(pair<int, int> id, const vector<vector<int> > &board) { //判断走这里可以合不合法
return board[id.first][id.second] == 0;
}
bool check3(pair<int, int> id, const vector<vector<int> > &board) { //判断这个格子是否有危险
int fx[8][2] = {{ -1, 0}, {1, 0}, {0, 1}, {0, -1}, { -1, -1}, {1, 1}, {1, -1}, { -1, 1}};
for (int i = id.first * 3; i < id.first * 3 + 3; i ++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j ++) {
for (int k = 0; k < 8; k ++) {
int x = i + fx[k][0], y = j + fx[k][1];
int xx = i + fx[k][0] * 2, yy = j + fx[k][1] * 2;
if (rule(id, x, y) && rule(id, xx, yy)) {
if (board[i][j] == -1 && board[x][y] == 0 && board[xx][yy] == -1) {
return 1;
} else if (board[i][j] == 0 && board[x][y] == -1 && board[xx][yy] == -1) {
return 1;
} else if (board[i][j] == -1 && board[x][y] == -1 && board[xx][yy] == 0) {
return 1;
}
}
}
}
}
return 0;
}
bool check5(pair<int, int> id, const vector<vector<int> > &board) { //判断这个格子我是否占优
int fx[8][2] = {{ -1, 0}, {1, 0}, {0, 1}, {0, -1}, { -1, -1}, {1, 1}, {1, -1}, { -1, 1}};
for (int i = id.first * 3; i < id.first * 3 + 3; i ++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j ++) {
for (int k = 0; k < 8; k ++) {
int x = i + fx[k][0], y = j + fx[k][1];
int xx = i + fx[k][0] * 2, yy = j + fx[k][1] * 2;
if (rule(id, x, y) && rule(id, xx, yy)) {
if (board[i][j] == 1 && board[x][y] == 0 && board[xx][yy] == 1) {
return 1;
} else if (board[i][j] == 0 && board[x][y] == 1 && board[xx][yy] == 1) {
return 1;
} else if (board[i][j] == 1 && board[x][y] == 1 && board[xx][yy] == 0) {
return 1;
}
}
}
}
}
return 0;
}
pair<int, int> solve(pair<int, int> id, const vector<vector<int> > &board) {
int fx[8][2] = {{ -1, 0}, {1, 0}, {0, 1}, {0, -1}, { -1, -1}, {1, 1}, {1, -1}, { -1, 1}};
for (int i = id.first * 3; i < id.first * 3 + 3; i ++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j ++) {
for (int k = 0; k < 8; k ++) {
int x = i + fx[k][0], y = j + fx[k][1];
int xx = i + fx[k][0] * 2, yy = j + fx[k][1] * 2;
if (rule(id, x, y) && rule(id, xx, yy)) {
if (board[i][j] == -1 && board[x][y] == 0 && board[xx][yy] == -1) {
return {x, y};
} else if (board[i][j] == 0 && board[x][y] == -1 && board[xx][yy] == -1) {
return {i, j};
} else if (board[i][j] == -1 && board[x][y] == -1 && board[xx][yy] == 0) {
return {xx, yy};
}
}
}
}
}
}
pair<int, int> solve2(pair<int, int> id, const vector<vector<int> > &board) {
int fx[8][2] = {{ -1, 0}, {1, 0}, {0, 1}, {0, -1}, { -1, -1}, {1, 1}, {1, -1}, { -1, 1}};
for (int i = id.first * 3; i < id.first * 3 + 3; i ++) {
for (int j = id.second * 3; j < id.second * 3 + 3; j ++) {
for (int k = 0; k < 8; k ++) {
int x = i + fx[k][0], y = j + fx[k][1];
int xx = i + fx[k][0] * 2, yy = j + fx[k][1] * 2;
if (rule(id, x, y) && rule(id, xx, yy)) {
if (board[i][j] == 1 && board[x][y] == 0 && board[xx][yy] == 1) {
return {x, y};
} else if (board[i][j] == 0 && board[x][y] == 1 && board[xx][yy] == 1) {
return {i, j};
} else if (board[i][j] == 1 && board[x][y] == 1 && board[xx][yy] == 0) {
return {xx, yy};
}
}
}
}
}
}
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
int x = id.first * 3, y = id.second * 3;
vector<pair<int, int> > jh;
if (x == -3 && y == -3) {
for (int i = 0; i < 3; i ++) {
for (int j = 0; j < 3; j ++) {
if (check3({i, j}, board)) {
return solve({i, j}, board);
}
}
}
for (int i = 0; i < 3; i ++) {
for (int j = 0; j < 3; j ++) {
if (check5({i, j}, board)) {
return solve2({i, j}, board);
}
}
}
for (int i = 0; i < 9; i ++) {
for (int j = 0; j < 9; j ++) {
if (check2({i, j}, board))jh.push_back({i, j});
}
}
return jh[rd() % jh.size()];
} else {
if (check3(id, board)) {
return solve(id, board);
}
if (check5(id, board)) {
return solve2(id, board);
}
for (int i = x; i < x + 3; i ++) {
for (int j = y; j < y + 3; j ++) {
if (check2({i, j}, board))jh.push_back({i, j});
}
}
return jh[rd() % jh.size()];
}
}
}
namespace ZHR {
int attack = 2;
//by ZHR
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pi;
mt19937 rd(random_device {}());
struct node {
int cf, qz = 0, fsqz = 0, ntf, rdid;
pi pos;
};
struct cmp {
bool operator()(node b, node a) {
if (a.cf != b.cf)return a.cf > b.cf;
if (attack == 1) {
if (a.fsqz != b.fsqz)return a.fsqz > b.fsqz;
if (a.qz != b.qz)return a.qz > b.qz;
} else {
if (a.qz != b.qz)return a.qz > b.qz;
if (a.fsqz != b.fsqz)return a.fsqz > b.fsqz;
}
if (a.ntf != b.ntf)return a.ntf > b.ntf;
return a.rdid > b.rdid;
}
};
// board 0:empty 1:my_own -1:enemy's
// id(0 -> 2, 0 -> 2) 表示当前要下的格子的坐标，(-1, -1)表示可以任意下
// 坐标从 0 开始
// 所有代码写在 namespace 里，step可以看做主函数
pi big;
vector<vector<int> > a;
bool legal(pi bg, pi lt) {
if (bg == big || big == make_pair(-1, -1)) {
int ax = bg.fi * 3 + lt.fi, ay = bg.se * 3 + lt.se;
if (a[ax][ay] == 0)return 1;
else return 0;
} else return 0;
}
int pure(pi bg, vector<vector<int> > v) {
int jx = bg.fi * 3, jy = bg.se * 3, tot[5];
tot[0] = tot[1] = tot[2] = tot[3] = 0;
for (int i = 0; i <= 2; i++) {
for (int j = 0; j <= 2; j++) {
if (v[jx + i][jy + j] == 1)tot[1]++;
else if (v[jx + i][jy + j] == -1)tot[2]++;
else tot[0]++;
}
}
if (tot[1] == 9)return 1;
if (tot[2] == 9)return -1;
return 0;
}
int calqz(pi bg, int &qz, int &fsqz, vector<vector<int> > v) {
int bx = bg.fi, by = bg.se;
for (int i = 0; i <= 2; i++) {
int res = pure(make_pair(bx, i), v);
if (res == 1)qz++;
else if (res == -1)fsqz++;
}
for (int i = 0; i <= 2; i++) {
int res = pure(make_pair(i, by), v);
if (res == 1)qz++;
else if (res == -1)fsqz++;
}
if (bx == by) {
for (int i = 0; i <= 2; i++) {
int res = pure(make_pair(i, i), v);
if (res == 1)qz++;
else if (res == -1)fsqz++;
}
}
if (bx + by == 2) {
for (int i = 0; i <= 2; i++) {
int res = pure(make_pair(i, 2 - i), v);
if (res == 1)qz++;
else if (res == -1)fsqz++;
}
}
}
int canfull(pi bg, vector<vector<int> > v) {
int jx = bg.fi * 3, jy = bg.se * 3;
//横竖
for (int i = 0; i < 3; i++) {
int tot = a[jx][jy + i] + a[jx + 1][jy + i] + a[jx + 2][jy + i];
if ((a[jx][jy + i] == 1 && a[jx + 1][jy + i] == 1 && a[jx + 2][jy + i] == 1))return (3 - attack);
if ((tot <= -1))return (3 - attack);
tot = a[jx + i][jy] + a[jx + i][jy + 1] + a[jx + i][jy + 2];
if ((a[jx + i][jy] == 1 && a[jx + i][jy + 1] == 1 && a[jx + i][jy + 2] == 1))return (3 - attack);
if ((tot <= -1))return (3 - attack);
}
//斜角
int tot = a[jx][jy] + a[jx + 1][jy + 1] + a[jx + 2][jy + 2];
if ((a[jx][jy] == 1 && a[jx + 1][jy + 1] == 1 && a[jx + 2][jy + 2] == 1))return (3 - attack);
if ((tot <= -1))return (3 - attack);
tot = a[jx][jy + 2] + a[jx + 1][jy + 1] + a[jx + 2][jy];
if ((a[jx][jy + 2] == 1 && a[jx + 1][jy + 1] == 1 && a[jx + 2][jy] == 1))return (3 - attack);
else if ((tot <= -1))return (3 - attack);
else return 0;
}
int full(pi bg, pi lt) {
if (legal(bg, lt)) {
int ax = bg.fi * 3 + lt.fi, ay = bg.se * 3 + lt.se;
vector<vector<int> > tmp;
tmp = a;
tmp[ax][ay] = 1;
return canfull(bg, tmp);
} else return 0;
}
pair<int, int> step(pair<int, int> id, const std::vector<std::vector<int> > &board) {
priority_queue<node, vector<node>, cmp>q;
big = id;
a = board;
for (int bx = 0; bx <= 2; bx++) {
for (int by = 0; by <= 2; by++) {
for (int i = 0; i <= 2; i++) {
for (int j = 0; j <= 2; j++) {
int nx = bx * 3 + i, ny = by * 3 + j;
if (legal(make_pair(bx, by), make_pair(i, j))) {
node tmp;
tmp.cf = full(make_pair(bx, by), make_pair(i, j));
vector<vector<int> > v = a;
v[nx][ny] = 1;
calqz(make_pair(bx, by), tmp.qz, tmp.fsqz, v);
tmp.ntf = canfull(make_pair(bx, by), v);
tmp.rdid = rd() % 1000000007;
tmp.pos = make_pair(nx, ny);
q.push(tmp);
}
}
}
}
}
if (!q.empty()) {
pi ans = q.top().pos;
return ans;
}
return { -1, -1};
}
#undef fi
#undef se
}
namespace CZH {
// board 0 1 -1
// id(0 -> 2, 0 -> 2) 表示当前要下的格子的坐标，(-1, -1)表示可以任意下
// 坐标从 0 开始
// 所有代码写在 namespace 里，step可以看做主函数
std::mt19937 rd;
vector<pair<int, int> > tr[9];
vector<pair<int, int> > fl[9];
vector<int> all;
int vis[9];
pair<int, int> id;
int num;
int a[9][3][3];
int b[9];
void addz(int x) {
for (int i = 0; i < 3; i++) {
if (a[x][i][0] == a[x][i][1] && a[x][i][0] == 1 && a[x][i][2] == 0) tr[x].push_back({i, 2});
if (a[x][i][0] == a[x][i][2] && a[x][i][0] == 1 && a[x][i][1] == 0) tr[x].push_back({i, 1});
if (a[x][i][2] == a[x][i][1] && a[x][i][1] == 1 && a[x][i][0] == 0) tr[x].push_back({i, 0});
}
for (int i = 0; i < 3; i++) {
if (a[x][0][i] == a[x][1][i] && a[x][0][i] == 1 && a[x][2][i] == 0) tr[x].push_back({2, i});
if (a[x][0][i] == a[x][2][i] && a[x][0][i] == 1 && a[x][1][i] == 0) tr[x].push_back({1, i});
if (a[x][2][i] == a[x][1][i] && a[x][1][i] == 1 && a[x][0][i] == 0) tr[x].push_back({0, i});
}
if (a[x][0][0] == a[x][1][1] && a[x][0][0] == 1 && a[x][2][2] == 0) tr[x].push_back({2, 2});
if (a[x][0][0] == a[x][2][2] && a[x][1][1] == 0 && a[x][0][0] == 1) tr[x].push_back({1, 1});
if (a[x][1][1] == a[x][2][2] && a[x][0][0] == 0 && a[x][1][1] == 1) tr[x].push_back({0, 0});
if (a[x][0][2] == a[x][1][1] && a[x][0][2] == 1 && a[x][2][0] == 0) tr[x].push_back({2, 0});
if (a[x][0][2] == a[x][2][0] && a[x][0][2] == 1 && a[x][1][1] == 0) tr[x].push_back({1, 1});
if (a[x][2][0] == a[x][1][1] && a[x][0][2] == 0 && a[x][1][1] == 1) tr[x].push_back({0, 2});
}
void addf(int x) {
for (int i = 0; i < 3; i++) {
if (a[x][i][0] == a[x][i][1] && a[x][i][0] == -1 && a[x][i][2] == 0) fl[x].push_back({i, 2});
if (a[x][i][0] == a[x][i][2] && a[x][i][0] == -1 && a[x][i][1] == 0) fl[x].push_back({i, 1});
if (a[x][i][2] == a[x][i][1] && a[x][i][1] == -1 && a[x][i][0] == 0) fl[x].push_back({i, 0});
}
for (int i = 0; i < 3; i++) {
if (a[x][0][i] == a[x][1][i] && a[x][0][i] == -1 && a[x][2][i] == 0) fl[x].push_back({2, i});
if (a[x][0][i] == a[x][2][i] && a[x][0][i] == -1 && a[x][1][i] == 0) fl[x].push_back({1, i});
if (a[x][2][i] == a[x][1][i] && a[x][1][i] == -1 && a[x][0][i] == 0) fl[x].push_back({0, i});
}
if (a[x][0][0] == a[x][1][1] && a[x][0][0] == -1 && a[x][2][2] == 0) fl[x].push_back({2, 2});
if (a[x][0][0] == a[x][2][2] && a[x][1][1] == 0 && a[x][0][0] == -1) fl[x].push_back({1, 1});
if (a[x][1][1] == a[x][2][2] && a[x][0][0] == 0 && a[x][1][1] == -1) fl[x].push_back({0, 0});
if (a[x][0][2] == a[x][1][1] && a[x][0][2] == -1 && a[x][2][0] == 0) fl[x].push_back({2, 0});
if (a[x][0][2] == a[x][2][0] && a[x][0][2] == -1 && a[x][1][1] == 0) fl[x].push_back({1, 1});
if (a[x][2][0] == a[x][1][1] && a[x][0][2] == 0 && a[x][1][1] == -1) fl[x].push_back({0, 2});
}
void addall(int x) {
for (int i = 0; i < 3; i++) {
if (b[0 + i] == b[3 + i] && b[0 + i] == -1 && b[6 + i] == 0) vis[6 + i] = 1;
if (b[0 + i] == b[6 + i] && b[0 + i] == -1 && b[3 + i] == 0) vis[3 + i] = 1;
if (b[3 + i] == b[6 + i] && b[3 + i] == -1 && b[0 + i] == 0) vis[0 + i] = 1;
}
for (int j = 0; j < 3; j++) {
int i = j * 3;
if (b[0 + i] == b[1 + i] && b[0 + i] == -1 && b[2 + i] == 0) vis[2 + i] = 1;
if (b[0 + i] == b[2 + i] && b[0 + i] == -1 && b[1 + i] == 0) vis[1 + i] = 1;
if (b[2 + i] == b[1 + i] && b[1 + i] == -1 && b[0 + i] == 0) vis[0 + i] = 1;
}
if (b[0] == b[4] && b[0] == -1 && b[8] == 0) vis[8] = 1;
if (b[0] == b[8] && b[8] == -1 && b[4] == 0) vis[4] = 1;
if (b[4] == b[8] && b[4] == -1 && b[0] == 0) vis[0] = 1;
}
pair<int, int> step(pair<int, int> id, const std::vector<std::vector<int>> &board) {
for (int k = 0; k < 9; k++) {
int x = k / 3, y = k % 3;
int f = -3;
for (int i = 3 * x; i < 3 * (x + 1); i++) {
for (int j = 3 * y; j < 3 * (y + 1); j++) {
if (f == -3) f = board[i][j];
if (f != board[i][j]) f = -2;
a[k][i % 3][j % 3] = board[i][j];
}
}
if (f != -2) b[k] = f;
}
num = id.first * 3 + id.second;
if (id.first == -1 && id.second == -1) num = 9;
for (int i = 0; i < 9; i++) {
if (b[i] == 0) addz(i), addf(i);
addall(i);
}
int f = 0;
for (int i = 0; i < 9; i++) {
if (tr[i].size() != 0 && fl[i].size() != 0) {
f = 1;
}
}
pair<int, int> ans;
if (num == 9) {
for (int i = 0; i < 9; i++) {
int x = i / 3;
int y = i % 3;
if (vis[i] == 1) {
if (tr[i].size() > 0) {
int e = rd() % tr[i].size();
if (board[tr[i][e].first + x * 3][tr[i][e].second + y] == 0)
ans = {tr[i][e].first + x * 3, tr[i][e].second + y};
break;
}
if (fl[i].size() > 0) {
int e = rd() % fl[i].size();
if (board[fl[i][e].first + x * 3][fl[i][e].second + y] == 0)
ans = {fl[i][e].first + x * 3, fl[i][e].second + y};
break;
}
}
}
if (ans.first == 0 && ans.second == 0) {
int x, y;
vector<pair<int, int>> v;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) v.push_back({i, j});
}
}
int e = rd() % v.size();
ans = {v[e].first, v[e].second};
}
} else if (f == 0) {
int xx = num / 3;
int yy = num % 3;
int x, y;
vector<pair<int, int>> v;
int x2 = num / 3, y2 = num % 3;
for (int i = x2 * 3; i < x2 * 3 + 3; i++) {
for (int j = y2 * 3; j < y2 * 3 + 3; j++) {
if (board[i][j] == 0) v.push_back({i, j});
}
}
int e = rd() % v.size();
ans = {v[e].first, v[e].second};
} else {
int f = 0;
vector<pair<int, int>> c;
for (int i = 0; i < fl[num].size(); i++) {
int dir = fl[num][i].first * 3 + fl[num][i].second;
if ((vis[dir] == 0 || fl[dir].size() == 0) && board[fl[num][i].first][fl[num][i].second] == 0) {
c.push_back({fl[num][i].first, fl[num][i].second});
}
}
if (c.size() != 0) {
int e = rd() % c.size();
int x = c[e].first;
int y = c[e].second;
int xx = num / 3;
int yy = num % 3;
ans = {xx * 3 + x, yy * 3 + y};
} else {
vector<pair<int, int>> c2;
for (int i = 0; i < tr[num].size(); i++) {
int dir = tr[num][i].first * 3 + tr[num][i].second;
if ((vis[dir] == 0 || fl[dir].size() == 0) && board[tr[num][i].first][tr[num][i].second] == 0) {
c2.push_back({tr[num][i].first, tr[num][i].second});
}
}
if (c2.size() != 0) {
int e = rd() % c2.size();
int x = c2[e].first;
int y = c2[e].second;
int xx = num / 3;
int yy = num % 3;
ans = {xx * 3 + x, yy * 3 + y};
} else {
int xx = num / 3;
int yy = num % 3;
int x, y;
vector<pair<int, int>> v;
int x2 = num / 3, y2 = num % 3;
for (int i = x2 * 3; i < x2 * 3 + 3; i++) {
for (int j = y2 * 3; j < y2 * 3 + 3; j++) {
if (board[i][j] == 0) v.push_back({i, j});
}
}
int e = rd() % v.size();
ans = {v[e].first, v[e].second};
}
}
}
// tiao();
//cout << ans.first << " " << ans.second;
return ans;
}
}
namespace GCH {
/*
就是满足以下原则：
1. 不能填一步就让对方赢。
2. 能填就填。
3. 同等情况下，优先选择不让对方填满大格子。
4. 同等情况下，优先选择不让对方随便走的格子。
按这个规则进行这一步的决策。
真实：
1. 能填则填。
2. 同等情况下，不让对方填满。
*/
mt19937 rd(time(NULL));
vector<vector<int> > v;
vector<int> b;
bool check(pair<int, int> id, vector<vector<int> > v) {
int i, j, x = id.first, y = id.second;
for (i = x * 3; i <= x * 3 + 2; i++) {
if (v[i][y * 3] == 1 && v[i][y * 3 + 1] == 1 && v[i][y * 3 + 2] == 1) return true;
}
for (j = y * 3; j <= y * 3 + 2; j++) {
if (v[x * 3][j] == 1 && v[x * 3 + 1][j] == 1 && v[x * 3 + 2][j] == 1) return true;
}
if (v[x * 3][y * 3] == 1 && v[x * 3 + 1][y * 3 + 1] == 1 && v[x * 3 + 2][y * 3 + 2] == 1) return true;
if (v[x * 3][y * 3 + 2] == 1 && v[x * 3 + 1][y * 3 + 1] == 1 && v[x * 3 + 2][y * 3] == 1) return true;
return false;
}
bool check2(pair<int, int> id, vector<vector<int> > v) {
int i, j, x = id.first, y = id.second;
for (i = x * 3; i <= x * 3 + 2; i++) {
if (v[i][y * 3] == -1 && v[i][y * 3 + 1] == -1) return true;
if (v[i][y * 3 + 1] == -1 && v[i][y * 3 + 2] == -1) return true;
}
for (j = y * 3; j <= y * 3 + 2; j++) {
if (v[x * 3][j] == -1 && v[x * 3 + 1][j] == -1) return true;
if (v[x * 3 + 1][j] == -1 && v[x * 3 + 2][j] == -1) return true;
}
if (v[x * 3][y * 3] == -1 && v[x * 3 + 1][y * 3 + 1] == -1) return true;
if (v[x * 3 + 1][y * 3 + 1] == -1 && v[x * 3 + 2][y * 3 + 2] == -1) return true;
if (v[x * 3][y * 3 + 2] == -1 && v[x * 3 + 1][y * 3 + 1] == -1) return true;
if (v[x * 3 + 1][y * 3 + 1] == -1 && v[x * 3 + 2][y * 3] == -1) return true;
return false;
}
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
int i, j, x = id.first, y = id.second, cnt = 0, sum = 0;
v.clear();
for (i = 0; i <= 8; i++) {
b.clear();
for (j = 0; j <= 8; j++) b.push_back(board[i][j]);
v.push_back(b);
}
if (x != -1) {
cnt = 0;
for (i = x * 3; i <= x * 3 + 2; i++) {
for (j = y * 3; j <= y * 3 + 2; j++) {
if (!v[i][j]) {
cnt++;
v[i][j] = 1;
if (check({i - x * 3, j - y * 3}, v) && !check2({i - x * 3, j - y * 3}, v)) return {i, j};
v[i][j] = 0;
}
}
}
for (i = x * 3; i <= x * 3 + 2; i++) {
for (j = y * 3; j <= y * 3 + 2; j++) {
if (!v[i][j]) {
v[i][j] = 1;
if (check({i - x * 3, j - y * 3}, v) && check2({i - x * 3, j - y * 3}, v)) return {i, j};
v[i][j] = 0;
}
}
}
if (cnt) {
int d = rd() % cnt + 1;
sum = 0;
for (i = x * 3; i <= x * 3 + 2; i++) {
for (j = y * 3; j <= y * 3 + 2; j++) {
if (v[i][j]) continue;
sum++;
if (sum == d) return {i, j};
}
}
}
cnt = 0;
for (i = 0; i <= 8; i++) {
for (j = 0; j <= 8; j++) {
if (!v[i][j]) {
cnt++;
v[i][j] = 1;
if (check({i / 3, j / 3}, v) && !check2({i / 3, j / 3}, v)) return {i, j};
v[i][j] = 0;
}
}
}
for (i = 0; i <= 8; i++) {
for (j = 0; j <= 8; j++) {
if (!v[i][j]) {
v[i][j] = 1;
if (check({i / 3, j / 3}, v) && check2({i / 3, j / 3}, v)) return {i, j};
v[i][j] = 0;
}
}
}
int d = rd() % cnt + 1;
sum = 0;
for (i = 0; i <= 8; i++) {
for (j = 0; j <= 8; j++) {
if (!v[i][j]) {
sum++;
if (sum == d) return {i, j};
}
}
}
} else {
cnt = 0;
for (i = 0; i <= 8; i++) {
for (j = 0; j <= 8; j++) {
if (!v[i][j]) {
cnt++;
v[i][j] = 1;
if (check({i / 3, j / 3}, v) && !check2({i / 3, j / 3}, v)) return {i, j};
v[i][j] = 0;
}
}
}
int d = rd() % cnt + 1;
sum = 0;
for (i = 0; i <= 8; i++) {
for (j = 0; j <= 8; j++) {
if (!v[i][j]) {
sum++;
if (sum == d) return {i, j};
}
}
}
}
}
}
namespace ZMR {
struct srander {
srander() {
srand(time(NULL));
}
} sr;
const int N = 9;
#define x first
#define y second
int control(pair<int, int> id, const vector<vector<int> > &board) {
//该函数返回值：0代表没占，1代表自己占了，-1代表别人占了
int x = id.x, y = id.y;
int p[3][3];
for (int i = 0; i <= 2; i++) {
for (int j = 0; j <= 2; j++) {
p[i][j] = board[i + 3 * x][j + 3 * y];
}
}
if (p[0][0] == p[0][1] && p[0][1] == p[0][2] && p[0][0])return p[0][0];
if (p[1][0] == p[1][1] && p[1][1] == p[1][2] && p[1][0])return p[1][0];
if (p[2][0] == p[2][1] && p[2][1] == p[2][2] && p[2][0])return p[2][0];
if (p[0][0] == p[1][0] && p[1][0] == p[2][0] && p[0][0])return p[0][0];
if (p[0][1] == p[1][1] && p[1][1] == p[2][1] && p[0][1])return p[0][1];
if (p[0][2] == p[1][2] && p[1][2] == p[2][2] && p[0][2])return p[0][2];
if (p[0][0] == p[1][1] && p[1][1] == p[2][2] && p[0][0])return p[0][0];
if (p[0][2] == p[1][1] && p[1][1] == p[2][0] && p[0][2])return p[0][2];
return 0;
}
int towin(pair<int, int> id, const vector<vector<int> > &board) {
//该函数返回值：表示需要多少步才能拿下该格 ，-1表示无法拿下
if (id.x == -1 || id.y == -1)return -1;
int t = control(id, board);
if (t == 1)return 0;
else if (t == -1)return -1;
int x = id.x, y = id.y;
int p[3][3];
for (int i = 0; i <= 2; i++) {
for (int j = 0; j <= 2; j++) {
p[i][j] = board[i + 3 * x][j + 3 * y];
}
}
if (p[0][0] + p[0][1] + p[0][2] == 2)return 1;
if (p[1][0] + p[1][1] + p[1][2] == 2)return 1;
if (p[1][0] + p[1][1] + p[1][2] == 2)return 1;
if (p[0][0] + p[1][0] + p[2][0] == 2)return 1;
if (p[0][1] + p[1][1] + p[2][1] == 2)return 1;
if (p[0][2] + p[1][2] + p[2][2] == 2)return 1;
if (p[0][0] + p[1][1] + p[2][2] == 2)return 1;
if (p[0][2] + p[1][1] + p[2][0] == 2)return 1;
if (p[0][0] + p[0][1] + p[0][2] == 1 && min(p[0][0], min(p[0][1], p[0][2])) >= 0)return 2;
if (p[1][0] + p[1][1] + p[1][2] == 1 && min(p[1][0], min(p[1][1], p[1][2])) >= 0)return 2;
if (p[2][0] + p[2][1] + p[2][2] == 1 && min(p[2][0], min(p[2][1], p[2][2])) >= 0)return 2;
if (p[0][0] + p[1][0] + p[2][0] == 1 && min(p[0][0], min(p[1][0], p[2][0])) >= 0)return 2;
if (p[0][1] + p[1][1] + p[2][1] == 1 && min(p[0][1], min(p[1][1], p[2][1])) >= 0)return 2;
if (p[0][2] + p[1][2] + p[2][2] == 1 && min(p[0][2], min(p[1][2], p[2][2])) >= 0)return 2;
if (p[0][0] + p[1][1] + p[2][2] == 1 && min(p[0][0], min(p[1][1], p[2][2])) >= 0)return 2;
if (p[0][2] + p[1][1] + p[2][0] == 1 && min(p[0][2], min(p[1][1], p[2][0])) >= 0)return 2;
if (p[0][0] + p[0][1] + p[0][2] == 0)return 3;
if (p[1][0] + p[1][1] + p[1][2] == 0)return 3;
if (p[1][0] + p[1][1] + p[1][2] == 0)return 3;
if (p[0][0] + p[1][0] + p[2][0] == 0)return 3;
if (p[0][1] + p[1][1] + p[2][1] == 0)return 3;
if (p[0][2] + p[1][2] + p[2][2] == 0)return 3;
if (p[0][0] + p[1][1] + p[2][2] == 0)return 3;
if (p[0][2] + p[1][1] + p[2][0] == 0)return 3;
else return -1;
}
bool compare(int a, int b) { //a is easier than b?
if (a == b)return 0;
if (a == -1)return -1;
if (b == -1)return 1;
return a < b;
}
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
int x = id.x, y = id.y;
vector<pair<int, int> > vs;
if (x == -1 || y == -1 || control(id, board)) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0)vs.push_back({i, j});
}
}
} else {
for (int i = 0; i <= 2; i++) {
for (int j = 0; j <= 2; j++) {
if (board[i + 3 * x][j + 3 * y] == 0)vs.push_back({i + 3 * x, j + 3 * y});
}
}
}
int p = rand();
if ((!control({0, 0}, board)) && (p % 5 <= 3))return vs[0];
else return vs[p % (vs.size())];
}
}
namespace YJR {
//余璟睿
// board 0 1 -1
// id(0 -> 2, 0 -> 2) 表示当前要下的格子的坐标，(-1, -1)表示可以任意下
// 坐标从 0 开始
// 所有代码写在 namespace 里，step可以看做主函数
int qwd[3][3], qqwd[3][3];
int wwd[3][3][3][3];
void zjpd(int x, int y, vector<vector<int> > board) {
for (int i = x * 3; i <= x * 3 + 2; i++) {
for (int j = y * 3; j <= y * 3 + 2; j++) {
if (board[i][j]) wwd[x][y][i - x * 3][j - y * 3] = -1e9;
if (board[i][j] == 1) {
qwd[x][y]++;
}
if (board[i][j] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) {
wwd[a][b][x][y]--;
}
}
}
}
int js = 0;
for (int i = x * 3; i <= x * 3 + 2; i++) {
for (int j = y * 3; j <= y * 3 + 2; j++) {
if (board[i][j])js++;
}
}
if (js == 9) qwd[x][y] = -1e9;
if (board[x * 3 + 1][y * 3 + 1] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) {
wwd[a][b][x][y]--;
}
}
if (board[x * 3 + 1][y * 3 + 1] == 1) {
qwd[x][y]++;
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++)wwd[a][b][x][y]++;
}
if (board[x * 3][y * 3] && board[x * 3][y * 3] == board[x * 3 + 1][y * 3 + 1] && board[x * 3][y * 3] == board[x * 3 + 2][y * 3 + 2]) {
qwd[x][y] = -1e9;
if (board[x * 3 + 1][y * 3 + 1] == 1)qqwd[x][y] = 1;
else qqwd[x][y] = -1;
return ;
}
if (board[x * 3 + 2][y * 3] && board[x * 3 + 2][y * 3] == board[x * 3 + 1][y * 3 + 1] && board[x * 3 + 2][y * 3] == board[x * 3][y * 3 + 2]) {
qwd[x][y] = -1e9;
if (board[x * 3 + 1][y * 3 + 1] == 1)qqwd[x][y] = 1;
else qqwd[x][y] = -1;
return ;
}
for (int i = x * 3; i <= x * 3 + 2; i++) { //行
if (board[i][y * 3] && board[i][y * 3] == board[i][y * 3 + 1] && board[i][y * 3] == board[i][y * 3 + 2]) {
qwd[x][y] = -1e9;
if (board[i][y * 3] == 1)qqwd[x][y] = 1;
else qqwd[x][y] = -1;
return ;
}
if (board[i][y * 3] == 1 && board[i][y * 3 + 1] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][i - x * 3][2] += 3;
qwd[x][y]++;
}
if (board[i][y * 3] == 1 && board[i][y * 3 + 2] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][i - x * 3][1] += 3;
qwd[x][y]++;
}
if (board[i][y * 3 + 1] == 1 && board[i][y * 3 + 2] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][i - x * 3][0] += 3;
qwd[x][y]++;
}
if (board[i][y * 3] == -1 && board[i][y * 3 + 1] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][i - x * 3][2] += 3;
qwd[x][y]++;
}
if (board[i][y * 3] == -1 && board[i][y * 3 + 2] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][i - x * 3][1] += 3;
qwd[x][y]++;
}
if (board[i][y * 3 + 1] == -1 && board[i][y * 3 + 2] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][i - x * 3][0] += 3;
qwd[x][y]++;
}
}
for (int i = y * 3; i <= y * 3 + 2; i++) { //列
if (board[x * 3][i] && board[x * 3][i] == board[x * 3 + 1][i] && board[x * 3][i] == board[x * 3 + 2][i]) {
qwd[x][y] = -1e9;
if (board[x * 3][i] == 1)qqwd[x][y] = 1;
else qqwd[x][y] = -1;
return ;
}
if (board[x * 3][i] == 1 && board[x * 3 + 1][i] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][2][i - y * 3] += 3;
qwd[x][y]++;
}
if (board[x * 3][i] == 1 && board[x * 3 + 2][i] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][1][i - y * 3] += 3;
qwd[x][y]++;
}
if (board[x * 3 + 1][i] == 1 && board[x * 3 + 2][i] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][0][i - y * 3] += 3;
qwd[x][y]++;
}
if (board[x * 3][i] == -1 && board[x * 3 + 1][i] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][2][i - y * 3] += 3;
qwd[x][y]++;
}
if (board[x * 3][i] == -1 && board[x * 3 + 2][i] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][1][i - y * 3] += 3;
qwd[x][y]++;
}
if (board[x * 3 + 1][i] == -1 && board[x * 3 + 2][i] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][0][i - y * 3] += 3;
qwd[x][y]++;
}
}
//右斜
if (board[x * 3][y * 3] == 1 && board[x * 3 + 1][y * 3 + 1] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][2][2] += 3;
qwd[x][y]++;
}
if (board[x * 3][y * 3] == 1 && board[x * 3 + 2][y * 3 + 2] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][1][1] += 3;
qwd[x][y]++;
}
if (board[x * 3 + 1][y * 3 + 1] == 1 && board[x * 3 + 2][y * 3 + 2] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][0][0] += 3;
qwd[x][y]++;
}
if (board[x * 3][y * 3] == 1 && board[x * 3 + 1][y * 3 + 1] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][2][2] += 3;
qwd[x][y]++;
}
if (board[x * 3][y * 3] == 1 && board[x * 3 + 2][y * 3 + 2] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][1][1] += 3;
qwd[x][y]++;
}
if (board[x * 3 + 1][y * 3 + 1] == 1 && board[x * 3 + 2][y * 3 + 2] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][0][0] += 3;
qwd[x][y]++;
}
//左斜
if (board[x * 3 + 2][y * 3] == 1 && board[x * 3 + 1][y * 3 + 1] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][0][2] += 3;
qwd[x][y]++;
}
if (board[x * 3][y * 3 + 2] == 1 && board[x * 3 + 1][y * 3 + 1] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][2][0] += 3;
qwd[x][y]++;
}
if (board[x * 3 + 2][y * 3] == 1 && board[x * 3][y * 3 + 2] == 1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][1][1] += 3;
qwd[x][y]++;
}
if (board[x * 3 + 2][y * 3] == -1 && board[x * 3 + 1][y * 3 + 1] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][0][2] += 3;
qwd[x][y]++;
}
if (board[x * 3][y * 3 + 2] == -1 && board[x * 3 + 1][y * 3 + 1] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][2][0] += 3;
qwd[x][y]++;
}
if (board[x * 3 + 2][y * 3] == -1 && board[x * 3][y * 3 + 2] == -1) {
for (int a = 0; a <= 2; a++)for (int b = 0; b <= 2; b++) wwd[a][b][x][y]--;
wwd[x][y][1][1] += 3;
qwd[x][y]++;
}
}
void qjpd(vector<vector<int> > board) {
for (int i = 0; i <= 2; i++) {
if (qqwd[i][0] == 1 && qqwd[i][1] == 1 && qqwd[i][2] == 0) {
qwd[i][2] += 10;
}
if (qqwd[i][0] == 1 && qqwd[i][2] == 1 && qqwd[i][1] == 0) {
qwd[i][1] += 10;
}
if (qqwd[i][1] == 1 && qqwd[i][2] == 1 && qqwd[i][0] == 0) {
qwd[i][0] += 10;
}
if (qqwd[i][0] == -1 && qqwd[i][1] == -1 && qqwd[i][2] == 0) {
qwd[i][2] += 10;
}
if (qqwd[i][0] == -1 && qqwd[i][2] == -1 && qqwd[i][1] == 0) {
qwd[i][1] += 10;
}
if (qqwd[i][1] == -1 && qqwd[i][2] == -1 && qqwd[i][0] == 0) {
qwd[i][0] += 10;
}
if (qqwd[0][i] == 1 && qqwd[1][i] == 1 && qqwd[2][i] == 0) {
qwd[2][i] += 10;
}
if (qqwd[0][i] == 1 && qqwd[2][i] == 1 && qqwd[1][i] == 0) {
qwd[1][i] += 10;
}
if (qqwd[1][i] == 1 && qqwd[2][i] == 1 && qqwd[0][i] == 0) {
qwd[0][i] += 10;
}
if (qqwd[0][i] == -1 && qqwd[1][i] == -1 && qqwd[2][i] == 0) {
qwd[2][i] += 10;
}
if (qqwd[0][i] == -1 && qqwd[2][i] == -1 && qqwd[1][i] == 0) {
qwd[1][i] += 10;
}
if (qqwd[1][i] == -1 && qqwd[2][i] == -1 && qqwd[0][i] == 0) {
qwd[0][i] += 10;
}
}
if (qqwd[0][0] == 1 && qqwd[1][1] == 1 && qqwd[2][2] == 0) {
qwd[2][2] += 10;
}
if (qqwd[0][0] == 1 && qqwd[2][2] == 1 && qqwd[1][1] == 0) {
qwd[1][1] += 10;
}
if (qqwd[1][1] == 1 && qqwd[2][2] == 1 && qqwd[0][0] == 0) {
qwd[0][0] += 10;
}
if (qqwd[0][0] == -1 && qqwd[1][1] == -1 && qqwd[2][2] == 0) {
qwd[2][2] += 10;
}
if (qqwd[0][0] == -1 && qqwd[2][2] == -1 && qqwd[1][1] == 0) {
qwd[1][1] += 10;
}
if (qqwd[1][1] == -1 && qqwd[2][2] == -1 && qqwd[0][0] == 0) {
qwd[0][0] += 10;
}
if (qqwd[2][0] == 1 && qqwd[1][1] == 1 && qqwd[0][2] == 0) {
qwd[0][2] += 10;
}
if (qqwd[2][0] == 1 && qqwd[0][2] == 1 && qqwd[1][1] == 0) {
qwd[1][1] += 10;
}
if (qqwd[0][2] == 1 && qqwd[1][1] == 1 && qqwd[2][0] == 0) {
qwd[2][0] += 10;
}
if (qqwd[2][0] == -1 && qqwd[1][1] == -1 && qqwd[0][2] == 0) {
qwd[0][2] += 10;
}
if (qqwd[2][0] == -1 && qqwd[0][2] == -1 && qqwd[1][1] == 0) {
qwd[1][1] += 10;
}
if (qqwd[0][2] == -1 && qqwd[1][1] == -1 && qqwd[2][0] == 0) {
qwd[2][0] += 10;
}
}
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
int i, j;
for (int a = 0; a <= 2; a++) {
for (int b = 0; b <= 2; b++) {
for (int c = 0; c <= 2; c++) {
for (int d = 0; d <= 2; d++) {
qwd[c][d] = wwd[a][b][c][d] = 9;
}
}
wwd[a][b][1][1]++;
}
}
qwd[1][1] = 10;
for (i = 0; i <= 2; i++)for (j = 0; j <= 2; j++) zjpd(i, j, board); //已经被占据的点
qjpd(board);
if (id.first == -1) { //任意下
int mx = -1e9;
for (i = 0; i <= 2; i++)for (j = 0; j <= 2; j++) {
if (mx < qwd[i][j]) {
mx = qwd[i][j];
id.first = i;
id.second = j;
}
}
}
pair<int, int> da;
int mx = -1e9;
for (i = 0; i <= 2; i++) {
for (j = 0; j <= 2; j++) {
if (mx < wwd[id.first][id.second][i][j]) {
mx = wwd[id.first][id.second][i][j];
da.first = id.first * 3 + i;
da.second = id.second * 3 + j;
}
}
}
return da;
}
}
namespace LZY {
static int t = 0;
class tool {
bool canfill(pair<int, int> id, pair<int, int> pos, const vector<vector<int>> &block) {
int lx, ly, rx, ry;
lx = id.first * 3;
ly = id.second * 3;
rx = lx + 2;
ry = ly + 2;
bool s1 = true;
for (int i = 0; i < 3; i++) {
s1 &= (block[i][pos.second - ly] == 1 || pos.first - lx == i);
}
bool s2 = true;
for (int i = 0; i < 3; i++) {
s2 &= (block[pos.first - lx][i] == 1 || pos.second - ly == i);
}
bool s3 = false, s4 = false;
if (pos.first - lx == pos.second - ly) {
for (int i = 0; i < 3; i++) {
s3 &= (block[i][i] == 1 || pos.first - lx == i);
}
}
if (pos.first - lx + pos.second - ly == 2) {
for (int i = 0; i < 3; i++) {
int j = 2 - i;
s4 &= (block[i][j] == 1 || pos.first - lx == i);
}
}
return s1 || s2 || s3 || s4;
}
public:
vector<vector<bool>> full(const vector<vector<int>> &board) {
vector<vector<bool>> res(3, vector<bool>(3));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int lx = i * 3, ly = j * 3;
int rx = lx + 2, ry = ly + 2;
bool s = true;
for (int x = lx; x <= rx; x++) {
for (int y = ly; y <= ry; y++) {
if (board[x][y] == 0) {
s = false;
break;
}
}
}
res[i][j] = s;
}
}
return res;
}
vector<vector<int>> block(pair<int, int> id, const vector<vector<int>> &board) {
vector<vector<int>> res;
int lx, ly, rx, ry;
lx = id.first * 3;
ly = id.second * 3;
rx = lx + 2;
ry = ly + 2;
res.resize(rx - lx + 1);
for (int i = lx; i <= rx; i++) {
res[i - lx].resize(ry - ly + 1);
for (int j = ly; j <= ry; j++) {
res[i - lx][j - ly] = board[i][j];
}
}
return res;
}
int val(pair<int, int> id, pair<int, int> pos, const vector<vector<int>> &bl, const vector<vector<bool>> &full, const vector<vector<int>> &board) {
t++;
int lx, ly;
lx = id.first * 3;
ly = id.second * 3;
bool k = canfill(id, pos, bl);
bool s = (id.first == 1 || id.second == 1);
int x = k * 12 + 20 - 17 * full[pos.first - lx][pos.second - ly] + 100 * (id.first == id.second && id.first == 1) * k + 30 * s;
return x;
}
};
pair<int, int> step(pair<int, int> id, const vector<vector<int>> &board) {
srand(time(0));
default_random_engine rd(rand());
srand(rd());
rd.seed(rand());
tool func;
vector<vector<bool>> full = func.full(board);
vector<pair<int, int>> can;
int lx, ly, rx, ry;
if (id.first == -1) {
lx = ly = 0;
rx = ry = 8;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (full[i][j]) {
continue;
}
can.push_back(step({i, j}, board));
}
}
} else {
lx = id.first * 3;
ly = id.second * 3;
rx = lx + 2;
ry = ly + 2;
vector<vector<int>> block = func.block(id, board);
for (int i = lx; i <= rx; i++) {
for (int j = ly; j <= ry; j++) {
if (board[i][j] == 0) {
int g = func.val(id, {i, j}, block, full, board);
for (int k = 1; k <= g; k++) {
can.push_back({i, j});
}
}
}
}
if (can.size() == 1) {
return can[0];
}
}
int x = rd() % can.size();
return can[x];
}
};
namespace WJW {
// wujiawei
// board 0 1 -1
// id(0 -> 2, 0 -> 2) 表示当前要下的格子的坐标，(-1, -1)表示可以任意下
// 坐标从 0 开始
// 所有代码写在 namespace 里，step可以看做主函数
// board 0:没有 1:自己的 -1:别人的
bool can(int x, int y, const std::vector<std::vector<int> > &board) {
return (board[x][y] == 0);
}
int cnt = 0;
std::pair<int, int> step(std::pair<int, int> id, const std::vector<std::vector<int> > &board) {
// std::vector<std::vector<int> > big(3);
// for(int i=0;i<3;i++)big[i].resize(3);
// for(int i=0;i<3;i++)
// for(int j=0;j<3;j++)
// {
// big[i][j]=board[i*3][j*3];
// for(int x=0;x<3;x++)
// for(int y=0;y<3;y++)
// if(board[i*3+x][j*3+y]!=board[i*3][j*3])
// {
// big[i][j]=0;
// break;
// }
// }
int ans[10][10];
memset(ans, 0, sizeof(ans));
if (id.first == -1 && id.second == -1) {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (!board[i][j]) {
if (i + 2 < 9 && board[i + 1][j] == board[i + 2][j])ans[i][j]++;
if (j + 2 < 9 && board[i][j + 1] == board[i][j + 2])ans[i][j]++;
if (i + 2 < 9 && j + 2 < 9 && board[i + 1][j + 1] == board[i + 2][j + 2])ans[i][j]++;
if (i - 2 >= 0 && board[i - 1][j] == board[i - 2][j])ans[i][j]++;
if (j - 2 >= 0 && board[i][j - 1] == board[i][j - 2])ans[i][j]++;
if (i - 2 >= 0 && j - 2 >= 0 && board[i - 1][j - 1] == board[i - 2][j - 2])ans[i][j]++;
}
}
} else {
for (int i = id.first * 3; i < id.first * 3 + 3; i++)
for (int j = id.second * 3; j < id.second * 3 + 3; j++) {
if (!board[i][j]) {
if (i + 2 < id.first * 3 + 3 && board[i + 1][j] == board[i + 2][j])ans[i][j]++;
if (j + 2 < id.second * 3 + 3 && board[i][j + 1] == board[i][j + 2])ans[i][j]++;
if (i + 2 < id.first * 3 + 3 && j + 2 < id.second * 3 + 3 && board[i + 1][j + 1] == board[i + 2][j + 2])ans[i][j]++;
if (i - 2 >= id.first * 3 && board[i - 1][j] == board[i - 2][j])ans[i][j]++;
if (j - 2 >= id.second * 3 && board[i][j - 1] == board[i][j - 2])ans[i][j]++;
if (i - 2 >= id.first * 3 && j - 2 >= id.second * 3 && board[i - 1][j - 1] == board[i - 2][j - 2])ans[i][j]++;
}
}
}
int x = 0, y = 0, Max = ans[0][0];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (ans[i][j] > Max)Max = ans[i][j], x = i, y = j;
if (!board[x][y])return {x, y};
vector<pair<int, int> > v;
if (id.first == -1 && id.second == -1) {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (!board[i][j])v.push_back({i, j});
} else {
for (int i = id.first * 3; i < id.first * 3 + 3; i++)
for (int j = id.second * 3; j < id.second * 3 + 3; j++)
if (!board[i][j])v.push_back({i, j});
}
srand((unsigned)time(NULL));
int t = 1LL * rand() * rand() % 123465;
while (t--)
srand((unsigned)time(NULL)*rand());
return v[rand() % v.size()];
}
};
namespace XZW {//Xiao肖智文
struct srander {
srander() {
srand(time(NULL));
}
} sranders;
const int N = 9;
bool check1(pair<int, int> id, const vector<vector<int> > &board) { //判断某个格子是否被占
for (int i = id.first * 3; i < id.first * 3 + 3; i ++) {
for (int j = id.second * 3; i < id.second * 3 + 3; j ++) {
if (board[i][j] != -1) {
return 0;
}
}
}
return 1;
}
bool check2(pair<int, int> id, const vector<vector<int> > &board) { //判断走这里可以合不合法
return board[id.first][id.second] == 0;
}
bool check3(pair<int, int> id, const vector<vector<int> > &board) { //判断这个格子是否有危险
int fx[8][2] = {{ -1, 0}, {1, 0}, {0, 1}, {0, -1}, { -1, -1}, {1, 1}, {1, -1}, { -1, 1}};
for (int i = id.first * 3; i < id.first * 3 + 3; i ++) {
for (int j = id.second * 3; i < id.second * 3 + 3; j ++) {
for (int k = 0; k < 8; k ++) {
int x = i + fx[k][0], y = j + fx[k][1];
if (x < 0 || y < 0 || x >= id.first * 3 + 3 || y >= id.second * 3 + 3 || board[i][j] != board[x][y])continue;
if (board[i][j] == -1)return 1;
}
}
}
return 0;
}
vector<pair<int, int> > check4(const vector<vector<int> > &board) { //判断有哪几个格子有危险
vector<pair<int, int> >res;
for (int i = 0; i < 3; i ++) {
for (int j = 0; j < 3; j ++) {
if (check3({i, j}, board))res.push_back({i, j});
}
}
return res;
}
bool check5(pair<int, int> id, const vector<vector<int> > &board) { //判断这个格子我是否占优
int fx[8][2] = {{ -1, 0}, {1, 0}, {0, 1}, {0, -1}, { -1, -1}, {1, 1}, {1, -1}, { -1, 1}};
for (int i = id.first * 3; i < id.first * 3 + 3; i ++) {
for (int j = id.second * 3; i < id.second * 3 + 3; j ++) {
for (int k = 0; k < 8; k ++) {
int x = i + fx[k][0], y = j + fx[k][1];
if (x < 0 || y < 0 || x >= id.first * 3 + 3 || y >= id.second * 3 + 3 || board[i][j] != board[x][y])continue;
if (board[i][j] == 1)return 1;
}
}
}
return 0;
}
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
int x = id.first * 3, y = id.second * 3;
vector<pair<int, int> > jh;
if (x == -3) {
pair<int, int> res;
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++) {
if (check2({i, j}, board))jh.push_back({i, j});
}
}
} else {
for (int i = x; i < x + 3; i ++) {
for (int j = y; j < y + 3; j ++) {
if (check2({i, j}, board))jh.push_back({i, j});
}
}
}
return jh[rand() % jh.size()];
}
}
namespace XR {
// Xr0701
typedef std::pair<int, int> PII;
int a[3][3][3][3];//棋盘
bool b[3][3];
int c[3][3];
bool cant[3][3];
bool lost;
PII qwq(PII);
void solve();
PII qvq();
PII step(PII id, const std::vector<std::vector<int> > &board) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
a[i / 3][j / 3][i % 3][j % 3] = board[i][j];
}
}
solve();
if (id.first >= 0) return qwq(id);
else return qvq();
}
bool check2(int, int, int);
bool check(int);
bool checkwin(int, int, int);
PII qwq(PII id) {
int x = id.first, y = id.second;
if (b[x][y]) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j]) continue;
a[x][y][i][j] = 1;
if (!check2(x, y, -1)) return {x * 3 + i, y * 3 + j};
a[x][y][i][j] = 0;
}
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cant[i][j] = 0;
if (a[x][y][i][j]) continue;
a[x][y][i][j] = 1;
if (checkwin(x, y, 1)) {
c[x][y] = 1;
if (check(1)) return {x * 3 + i, y * 3 + j};
c[x][y] = 0;
}
a[x][y][i][j] = 0;
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j]) continue;
a[x][y][i][j] = 1;
if (checkwin(x, y, 1)) {
if (b[i][j]) {
c[i][j] = -1;
if (!check(-1)) {
return {x * 3 + i, y * 3 + j};
}
cant[i][j] = 1;
c[i][j] = 0;
} else {
return {x * 3 + i, y * 3 + j};
}
}
a[x][y][i][j] = 0;
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j] || cant[i][j] || b[i][j] || (c[i][j] && lost)) continue;
a[x][y][i][j] = 1;
if (check2(x, y, 1)) {
return {x * 3 + i, y * 3 + j};
}
a[x][y][i][j] = 0;
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j] || cant[i][j] || (c[i][j] && lost) || b[i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j] || (c[i][j] && lost) || b[i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
return { -1, -1};
}
inline bool check2(int i, int j, int op) {
if (op == 1) {
if (a[i][j][0][0] + a[i][j][0][1] + a[i][j][0][2] >= 2) {
return 1;
}
if (a[i][j][1][0] + a[i][j][1][1] + a[i][j][1][2] >= 2) {
return 1;
}
if (a[i][j][2][0] + a[i][j][2][1] + a[i][j][2][2] >= 2) {
return 1;
}
if (a[i][j][0][0] + a[i][j][1][0] + a[i][j][2][0] >= 2) {
return 1;
}
if (a[i][j][0][1] + a[i][j][1][1] + a[i][j][2][1] >= 2) {
return 1;
}
if (a[i][j][0][2] + a[i][j][1][2] + a[i][j][2][2] >= 2) {
return 1;
}
if (a[i][j][0][0] + a[i][j][1][1] + a[i][j][2][2] >= 2) {
return 1;
}
if (a[i][j][0][2] + a[i][j][1][1] + a[i][j][2][0] >= 2) {
return 1;
}
} else {
if (a[i][j][0][0] + a[i][j][0][1] + a[i][j][0][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][1][0] + a[i][j][1][1] + a[i][j][1][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][2][0] + a[i][j][2][1] + a[i][j][2][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][0] + a[i][j][1][0] + a[i][j][2][0] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][1] + a[i][j][1][1] + a[i][j][2][1] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][2] + a[i][j][1][2] + a[i][j][2][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][0] + a[i][j][1][1] + a[i][j][2][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][2] + a[i][j][1][1] + a[i][j][2][0] <= -2) {
b[i][j] = 1;
}
}
return 0;
}
inline void solve() {
lost = 0;
//pan duan dui fang zai na ge da ge zi you lian er
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[i][j][0][0] + a[i][j][0][1] + a[i][j][0][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][1][0] + a[i][j][1][1] + a[i][j][1][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][2][0] + a[i][j][2][1] + a[i][j][2][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][0] + a[i][j][1][0] + a[i][j][2][0] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][1] + a[i][j][1][1] + a[i][j][2][1] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][2] + a[i][j][1][2] + a[i][j][2][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][0] + a[i][j][1][1] + a[i][j][2][2] <= -2) {
b[i][j] = 1;
}
if (a[i][j][0][2] + a[i][j][1][1] + a[i][j][2][0] <= -2) {
b[i][j] = 1;
}
if (b[i][j]) lost = 1;
}
}
//shi fou zhan ling
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
c[i][j] = a[i][j][0][0];
for (int k = 0; k < 3; ++k) {
for (int l = 0; l < 3; ++l) {
if (a[i][j][k][l] != c[i][j]) c[i][j] = 0;
}
}
}
}
}
inline bool check(int op) {
if (c[0][0] == c[0][1] && c[0][1] == c[0][2] && c[0][1] == op) return 1;
if (c[1][0] == c[1][1] && c[1][1] == c[1][2] && c[1][1] == op) return 1;
if (c[2][0] == c[2][1] && c[2][1] == c[2][2] && c[2][1] == op) return 1;
if (c[0][0] == c[1][0] && c[1][0] == c[2][0] && c[2][0] == op) return 1;
if (c[0][1] == c[1][1] && c[1][1] == c[2][1] && c[2][1] == op) return 1;
if (c[0][2] == c[1][2] && c[1][2] == c[2][2] && c[2][2] == op) return 1;
if (c[0][0] == c[1][1] && c[1][1] == c[2][2] && c[2][2] == op) return 1;
if (c[0][2] == c[1][1] && c[1][1] == c[2][0] && c[2][0] == op) return 1;
return 0;
}
inline bool checkwin(int x, int y, int op) { //neng fou zhan ling
if (a[x][y][0][0] == a[x][y][0][1] && a[x][y][0][1] == a[x][y][0][2] && a[x][y][0][1] == op) return 1;
if (a[x][y][1][0] == a[x][y][1][1] && a[x][y][1][1] == a[x][y][1][2] && a[x][y][1][1] == op) return 1;
if (a[x][y][2][0] == a[x][y][2][1] && a[x][y][2][1] == a[x][y][2][2] && a[x][y][2][1] == op) return 1;
if (a[x][y][0][0] == a[x][y][1][0] && a[x][y][1][0] == a[x][y][2][0] && a[x][y][2][0] == op) return 1;
if (a[x][y][0][1] == a[x][y][1][1] && a[x][y][1][1] == a[x][y][2][1] && a[x][y][2][1] == op) return 1;
if (a[x][y][0][2] == a[x][y][1][2] && a[x][y][1][2] == a[x][y][2][2] && a[x][y][2][2] == op) return 1;
if (a[x][y][0][0] == a[x][y][1][1] && a[x][y][1][1] == a[x][y][2][2] && a[x][y][2][2] == op) return 1;
if (a[x][y][0][2] == a[x][y][1][1] && a[x][y][1][1] == a[x][y][2][0] && a[x][y][2][0] == op) return 1;
return 0;
}
PII qvq() {
std::vector<PII> ans;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (check2(i, j, 1)) ans.push_back({i, j});
cant[i][j] = 0;
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (!b[i][j] || c[i][j]) continue;
c[i][j] = -1;
cant[i][j] = check(-1);
c[i][j] = 0;
}
}
if (ans.empty()) {
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (cant[i][j] || a[x][y][i][j] || (c[i][j] && lost) || b[i][j]) continue;
a[x][y][i][j] = 1;
if (check2(x, y, i)) {
return {x * 3 + i, y * 3 + j};
}
a[x][y][i][j] = 0;
}
}
}
}
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (cant[i][j] || a[x][y][i][j] || (c[i][j] && lost) || b[i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
}
}
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j] || (c[i][j] && lost) || b[i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
}
}
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
}
}
return { -1, -1};
}
for (PII l : ans) {
int x = l.first, y = l.second;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (cant[i][j] || a[x][y][i][j] || (c[i][j] && lost) || b[i][j]) continue;
a[x][y][i][j] = 1;
if (checkwin(x, y, 1)) {
return {x * 3 + i, y * 3 + j};
}
a[x][y][i][j] = 0;
}
}
}
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j] || (c[i][j] && lost) || b[i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
}
}
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (a[x][y][i][j]) continue;
return {x * 3 + i, y * 3 + j};
}
}
}
}
return { -1, -1};
}
};
namespace GL {
vector<vector<int>> mp;
int Full[4][4];
inline bool Can_occupy_this_board(int xx, int yy) {
int idx = xx / 3, idy = yy / 3, xb = idx * 3, xe = xb + 3, yb = idy * 3, ye = yb + 3;
int temp = mp[xx][yy];
mp[xx][yy] = 1;
int x, y;
for (x = xb; x < xe; x++) {//line
for (y = yb; y < ye; y++)
if (mp[x][y] != 1) goto Next1;
mp[xx][yy] = temp;
return true;
Next1:;
} for (y = yb; y < ye; y++) {//high
for (x = xb; x < xe; x++)
if (mp[x][y] != 1) goto Next2;
mp[xx][yy] = temp;
return true;
Next2:;
} x = xb, y = yb;
if (mp[x][y] == 1 && mp[x + 1][y + 1] == 1 && mp[x + 2][y + 2] == 1) {
mp[xx][yy] = temp;
return true;
}
x = xb, y = ye;
if (mp[x][y] == 1 && mp[x + 1][y - 1] == 1 && mp[x + 2][y - 2] == 1) {
mp[xx][yy] = temp;
return true;
} mp[xx][yy] = temp;
return false;
} inline bool Can_blockage_you(int xx, int yy) {
int idx = xx / 3, idy = yy / 3, xb = idx * 3, xe = xb + 3, yb = idy * 3, ye = yb + 3;
int x, y;
for (x = xx, y = yb; y < ye; y++)
if (mp[x][y] != -1) goto Next1;
return true;
Next1:;
for (y = yy, x = xb; x < xe; x++)
if (mp[x][y] != -1) goto Next2;
return true;
Next2:;
x = xb, y = yb;
if (mp[x][y] == -1 && mp[x + 1][y + 1] == -1 && mp[x + 2][y + 2] == -1)
if (x <= xx && xx <= x + 2 && y <= yy && yy <= y + 2) return true;
x = xb, y = ye;
if (mp[x][y] == -1 && mp[x + 1][y - 1] == -1 && mp[x + 2][y - 2] == -1) {
if (x <= xx && xx <= x + 2 && y - 2 <= yy && yy <= y) return true;
}
return false;
} inline bool You_can_occupy_this_board(int xx, int yy) {
int idx = xx / 3, idy = yy / 3, xb = idx * 3, xe = xb + 3, yb = idy * 3, ye = yb + 3;
int temp = mp[xx][yy];
mp[xx][yy] = -1;
int x, y;
for (x = xb; x < xe; x++) {//line
for (y = yb; y < ye; y++)
if (mp[x][y] != -1) goto Next1;
mp[xx][yy] = temp;
return true;
Next1:;
}
for (y = yb; y < ye; y++) {//high
for (x = xb; x < xe; x++)
if (mp[x][y] != -1) goto Next2;
mp[xx][yy] = temp;
return true;
Next2:;
}
x = xb, y = yb;
if (mp[x][y] == -1 && mp[x + 1][y + 1] == -1 && mp[x + 2][y + 2] == -1)
if (x <= xx && xx <= x + 2 && y <= yy && yy <= y + 2) return true;
x = xb, y = ye;
if (mp[x][y] == -1 && mp[x + 1][y - 1] == -1 && mp[x + 2][y - 2] == -1)
if (x <= xx && xx <= x + 2 && y - 2 <= yy && yy <= y) return true;
mp[xx][yy] = temp;
return false;
} inline bool You_can_occupy_this_board2(int idx, int idy) {
int xb = idx * 3, xe = xb + 3, yb = idy * 3, ye = yb + 3;
for (int x = xb; x < xe; x++)
for (int y = yb; y < ye; y++)
if (You_can_occupy_this_board(x, y)) return true;
return false;
} inline bool Importance(int idx, int idy, int pl) {
int temp = Full[idx][idy];
Full[idx][idy] = pl;
int x, y;
for (x = 0; x < 3; x++) {//line
for (y = 0; y < 3; y++)
if (Full[x][y] != pl) goto Next1;
Full[idx][idy] = temp;
return true;
Next1:;
} for (y = 0; y < 3; y++) {//high
for (x = 0; x < 3; x++)
if (Full[x][y] != pl) goto Next2;
Full[idx][idy] = temp;
return true;
Next2:;
} x = 0, y = 0;
if (Full[x][y] == pl && Full[x + 1][y + 1] == pl && Full[x + 2][y + 2] == pl) {
Full[idx][idy] = temp;
return true;
} x = 0, y = 2;
if (Full[x][y] == pl && Full[x + 1][y - 1] == pl && Full[x + 2][y - 2] == pl) {
Full[idx][idy] = temp;
return true;
}
Full[idx][idy] = temp;
return false;
} inline bool Not_death(int xx, int yy) {
int idx = xx / 3, idy = yy / 3, xb = idx * 3, xe = xb + 3, yb = idx * 3, ye = yb + 3, x, y;
for (x = xb; x < xe; x++)
for (y = yb; y < ye; y++)
if (!mp[x][y]) goto Not_all;
for (x = 0; x < 9; x++)
for (y = 0; y < 9; y++)
if (Importance(x / 3, y / 3, -1) && You_can_occupy_this_board(x, y))
return false;
Not_all:;
if (Importance(idx, idy, -1))
for (x = xb; x < xe; x++)
for (y = yb; y < ye; y++)
if (You_can_occupy_this_board(x, y))
return false;
return true;
} pair<int, int> step(const pair<int, int> id, const vector<vector<int>> &board) {
srand(time(NULL));
mp = board;
int idx = id.first, idy = id.second, x, y;
vector<pair<int, int>> place;
for (int i = 0, j, temp; i < 3; i++) {
for (j = 0; j < 3; j++) {
Full[i][j] = temp = mp[i * 3][j * 3];
for (x = i * 3; x < i * 3 + 3; x++)
for (y = j * 3; y < j * 3 + 3; y++)
if (mp[x][y] != temp) {
Full[i][j] = false;
goto Next1;
}
Next1:;
}
} if (idx == -1) {
for (x = 0; x < 9; x++)
for (y = 0; y < 9; y++) {
if (!mp[x][y]) {
if (Can_occupy_this_board(x, y) && Importance(x / 3, y / 3, 1)) return {x, y};
if (Not_death(x, y)) place.emplace_back(make_pair(x, y));
}
}
for (pair<int, int> node : place) {
x = node.first, y = node.second;
if (Can_occupy_this_board(x, y)) return {x, y};
} for (pair<int, int> node : place) {
x = node.first, y = node.second;
if (Can_blockage_you(x, y)) return {x, y};
} while (x = rand() % 9, y = rand() % 9)
if (!mp[x][y] && !Full[x / 3][y / 3] && !Importance(x / 3, y / 3, -1)) return {x, y};
for (x = 0; x < 9; x++)
for (y = 0; y < 9; y++)
if (!mp[x][y] && !Full[x / 3][y / 3] && !Importance(x / 3, y / 3, -1))
return {x, y};
if (place.size()) return place[rand() % place.size()];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) if (!mp[i][j]) place.emplace_back(make_pair(i, j));
return place[rand() % place.size()];
} int xb = idx * 3, xe = xb + 3, yb = idy * 3, ye = yb + 3;
for (x = xb; x < xe; x++)
for (y = yb; y < ye; y++)
if (!mp[x][y]) {
if (Importance(idx, idy, 1) && Can_occupy_this_board(x, y)) return {x, y};
if (!Full[x - idx * 3][y - idy * 3] && Not_death(x, y) && (!You_can_occupy_this_board2(x - idx * 3, y - idy * 3) || !Importance(x - idx * 3, y - idy * 3, -1)))
place.emplace_back(make_pair(x, y));
}
for (pair<int, int> node : place) {
x = node.first, y = node.second;
if (Can_occupy_this_board(x, y) && !You_can_occupy_this_board2(x - idx * 3, y - idy * 3)) return {x, y};
}
for (pair<int, int> node : place) {
x = node.first, y = node.second;
if (Can_blockage_you(x, y) && !You_can_occupy_this_board2(x - idx * 3, y - idy * 3)) return {x, y};
}
for (x = xb; x < xe; x++)
for (y = yb; y < ye; y++)
if (!mp[x][y] && !Full[x - idx * 3][y - idy * 3] && !Importance(x - idx * 3, y - idx * 3, -1) && !You_can_occupy_this_board2(x - idx * 3, y - idy * 3))
return {x, y};
if (place.size()) return place[rand() % place.size()];
for (int i = xb; i < xe; i++)
for (int j = yb; j < ye; j++) if (!mp[i][j]) place.emplace_back(make_pair(i, j));
return place[rand() % place.size()];
}
};
namespace QYZY {
// version:1.0
// author:qyzy/___Furina___
// introduce:The first drop is at the four corners, and then the drop is on the four sides.
// target:Win first in the middle square, prevent others from winning, and finally try to win in a losing situation
// awa
#define N 10
#define I_love_Furina return
#define forever 0
#define foreverr 1
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair
vector<vector<int> > b(3), p(3);
vector<PII> chs, bs;
int tot = 0, xh;
inline void init() {
srand(time(0));
for (int i = 0; i <= 2; i++)for (int j = 0; j <= 2; j++)b[i].emplace_back(0), p[i].emplace_back(0);
// for(int i=0;i<=2;i++){for(int j=0;j<=2;j++)cout<<b[i][j]<<" ";cout<<endl;}
I_love_Furina;
}
inline void pd(const vector<vector<int> > mp) {
int flag = 1;
for (int i = 0; i <= 8; i++)for (int j = 0; j <= 8; j++)if (mp[i][j] != 0) {
flag = 0;
break;
}
if (flag)xh = 1;
else tot++, xh = -1;
I_love_Furina ;
}
inline int check_win(int sx, int ex, int sy, int ey, const vector<vector<int> >mp) {
for (int i = sx; i <= ex; i++) {
int st = mp[i][sy], flag = 1;
if (st == 0)continue;
for (int j = sy + 1; j <= ey; j++)if (mp[i][j] != st) {
flag = 0;
break;
}
if (flag)I_love_Furina st;
}
for (int i = sy; i <= ey; i++) {
int st = mp[sx][i], flag = 1;
if (st == 0)continue;
for (int j = sx + 1; j <= ex; j++)if (mp[j][i] != st) {
flag = 0;
break;
}
if (flag)I_love_Furina st;
}
if (mp[sx][sy] == mp[sx + 1][sy + 1] && mp[sx][sy] == mp[ex][ey] && mp[sx][sy] != 0)I_love_Furina mp[sx][sy];
if (mp[sx][ey] == mp[sx + 1][ey - 1] && mp[sx][ey] == mp[ex][sy] && mp[sx][ey] != 0)I_love_Furina mp[sx][ey];
I_love_Furina forever;
}
inline int check_all_win(const vector<vector<int> > mp) {
int sx = 0, sy = 0, ex = 2, ey = 2;
for (int i = sx; i <= ex; i++) {
int st = mp[i][sy], flag = 1;
if (st == 0)continue;
for (int j = sy + 1; j <= ey; j++)if (mp[i][j] != st) {
flag = 0;
break;
}
if (flag)I_love_Furina st;
}
for (int i = sy; i <= ey; i++) {
int st = mp[sx][i], flag = 1;
if (st == 0)continue;
for (int j = sx + 1; j <= ex; j++)if (mp[j][i] != st) {
flag = 0;
break;
}
if (flag)I_love_Furina st;
}
if (mp[sx][sy] == mp[sx + 1][sy + 1] && mp[sx][sy] == mp[ex][ey] && mp[sx][sy] != 0)I_love_Furina mp[sx][sy];
if (mp[sx][ey] == mp[sx + 1][ey - 1] && mp[sx][ey] == mp[ex][sy] && mp[sx][ey] != 0)I_love_Furina mp[sx][ey];
I_love_Furina forever;
}
inline int try_step(int x, int y, int px, int py, vector<vector<int> > mp) {
int canwin = 0;
mp[x][y] = xh;
vector<vector<int> > op(3);
for (int i = px * 3; i <= px * 3 + 2; i++)for (int j = py * 3; j <= py * 3 + 2; j++)op[i - px * 3].emplace_back(mp[i][j]);
if (check_win(px * 3, py * 3, px * 3 + 2, py * 3 + 2, mp)) {
for (int i = 0; i <= 2; i++)for (int j = 0; j <= 2; j++)p[i][j] = check_win(i * 3, i * 3 + 2, j * 3, j * 3 + 2, mp);
if (check_all_win(p) == xh)I_love_Furina foreverr;
PII id = {x % 3, y % 3};
if (b[id.fi][id.se] != 0) {
for (int i = 0; i <= 8; i++)for (int j = 0; j <= 8; j++) {
if (mp[i][j] != 0 || p[i / 3][j / 3] != 0)continue;
mp[i][j] = -xh;
for (int ii = 0; ii <= 2; ii++)for (int jj = 0; jj <= 2; jj++)p[ii][jj] = check_win(ii * 3, ii * 3 + 2, jj * 3, jj * 3 + 2, mp);
mp[i][j] = 0;
if (check_all_win(p) == -xh)I_love_Furina - 1;
else if (check_all_win(p) == xh)I_love_Furina foreverr;;
}
I_love_Furina forever;
}
for (int i = id.fi * 3; i <= id.fi * 3 + 2; i++)
for (int j = id.se * 3; j <= id.se * 3 + 2; j++) {
if (mp[i][j] != 0)continue;
mp[i][j] = -xh;
for (int ii = 0; ii <= 2; ii++)for (int jj = 0; jj <= 2; jj++)p[ii][jj] = check_win(ii * 3, ii * 3 + 2, jj * 3, jj * 3 + 2, mp);
mp[i][j] = 0;
if (check_all_win(p) == -xh)I_love_Furina - 1;
else if (check_all_win(p) == xh)I_love_Furina foreverr;;
}
I_love_Furina forever;
} else {
PII id = {x % 3, y % 3};
if (b[id.fi][id.se] != 0) {
for (int i = 0; i <= 8; i++)for (int j = 0; j <= 8; j++) {
if (mp[i][j] != 0 || p[i / 3][j / 3] != 0)continue;
mp[i][j] = -xh;
for (int ii = 0; ii <= 2; ii++)for (int jj = 0; jj <= 2; jj++)p[ii][jj] = check_win(ii * 3, ii * 3 + 2, jj * 3, jj * 3 + 2, mp);
mp[i][j] = 0;
if (check_all_win(p) == -xh)I_love_Furina - 1;
else if (check_all_win(p) == xh)I_love_Furina foreverr;;
}
I_love_Furina forever;
}
for (int i = id.fi * 3; i <= id.fi * 3 + 2; i++)
for (int j = id.se * 3; j <= id.se * 3 + 2; j++) {
if (mp[i][j] != 0)continue;
mp[i][j] = -xh;
for (int ii = 0; ii <= 2; ii++)for (int jj = 0; jj <= 2; jj++)p[ii][jj] = check_win(ii * 3, ii * 3 + 2, jj * 3, jj * 3 + 2, mp);
mp[i][j] = 0;
if (check_all_win(p) == -xh)I_love_Furina - 1;
else if (check_all_win(p) == xh)I_love_Furina foreverr;;
}
I_love_Furina forever;
}
mp[x][y] = 0;
I_love_Furina forever;
}
inline PII step(PII id, const vector<vector<int> > &mp) {
chs.clear(), bs.clear();
PII ans = { -1, -1};
if (tot == 0)init();
pd(mp);
for (int i = 0; i <= 2; i++)for (int j = 0; j <= 2; j++)b[i][j] = check_win(i * 3, i * 3 + 2, j * 3, j * 3 + 2, mp);
if (tot == 0)ans = {5, 5};
else if (id.fi == -1) {
for (int i = 3; i <= 5; i++) {
if (ans.fi != -1)break;
for (int j = 3; j <= 5; j++) {
if (mp[i][j] != 0 || b[1][1])continue;
int rt = try_step(i, j, i / 3, j / 3, mp);
if (rt == 1) {
ans = {i, j};
break;
} else if (rt == 0)chs.push_back({i, j});
else bs.push_back({i, j});
}
}
for (int i = 0; i <= 8; i++) {
if (ans.fi != -1)break;
for (int j = 0; j <= 8; j++) {
if (mp[i][j] != 0 || b[i / 3][j / 3] != 0 || i / 3 == 1 && j / 3 == 1)continue;
int rt = try_step(i, j, i / 3, j / 3, mp);
if (rt == 1) {
ans.fi = i, ans.se = j;
break;
} else if (rt == 0)chs.push_back({i, j});
else bs.push_back({i, j});
}
}
} else {
for (int i = id.fi * 3; i <= id.fi * 3 + 2; i++) {
for (int j = id.se * 3; j <= id.se * 3 + 2; j++) {
if (mp[i][j] != 0)continue;
int rt = try_step(i, j, i / 3, j / 3, mp);
if (rt == 1) {
ans.fi = i, ans.se = j;
break;
} else if (rt == 0)chs.push_back({i, j});
else bs.push_back({i, j});
}
}
}
if (ans.fi == -1) {
vector<PII> awa;
for (PII i : chs) {
awa.emplace_back(i);
if (i.fi != 1 && i.fi != 4 && i.fi != 7 && i.se != 1 && i.se != 4 && id.se != 7)awa.emplace_back(i);
}
random_shuffle(awa.begin(), awa.end());
if (awa.size())ans = awa[0];
else ans = bs[0];
}
tot += 2;
I_love_Furina ans;
}
#undef N
#undef I_love_Furina
#undef forever
#undef foreverr
#undef PII
#undef fi
#undef se
#undef mk
}
namespace Rand {
struct srandd {
srandd() {
srand(time(NULL));
}
} sr;
mt19937 rnd(rand());
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
if (id.first == -1) {
pii res;
res.first = rnd() % 9, res.second = rnd() % 9;
while (board[res.first][res.second] != 0) res.first = rnd() % 9, res.second = rnd() % 9;
return res;
} else {
pii res;
int sx = id.first * 3, sy = id.second * 3;
res.first = sx + rnd() % 3, res.second = sy + rnd() % 3;
while (board[res.first][res.second] != 0) res.first = sx + rnd() % 3, res.second = sy + rnd() % 3;
return res;
}
}
}
namespace Human {
pair<int, int> step(pair<int, int> id, const vector<vector<int> > &board) {
if (id.first != -1) printf("\nyou have to put chess into the check from (%d,%d) to (%d,%d)\n", id.first * 3, id.second * 3, id.first * 3 + 2, id.second * 3 + 2);
else printf("\nyou can put chess into any empty place you want!\n");
printf("please input the position that you would put a chess: ");
int x, y;
cin >> x >> y;
while (x < 0 || x > 8 || y < 0 || y > 8 || board[x][y] != 0 || (id.first != -1 && (x / 3 != id.first || y / 3 != id.second))) {
printf("the placement is illegal! ignoring...\n");
printf("please input again: ");
cin >> x >> y;
}
return make_pair(x, y);
}
}
int filled[3][3];
vector<vector<int> > board;
inline pii trans(pii x) {
if (x.first < 0 || x.second < 0) return make_pair(-1, -1);
pii res = make_pair(x.first % 3, x.second % 3);
int sx = res.first * 3, sy = res.second * 3;
bool flag = true;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
int x = sx + i, y = sy + j;
if (board[x][y] == 0) {
flag = false;
break;
}
}
return flag ? make_pair(-1, -1) : res;
}
inline void print_board(const vector<vector<int>> &board, int now) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) putchar('\n');
if (i == 0) puts(" \\ 012 345 678 (y)");
printf(" %d ", i);
for (int j = 0; j < 9; j++) {
if (j % 3 == 0) putchar(' ');
if (board[i][j] == now) putchar('X');
else if (board[i][j] != 0) putchar('O');
else putchar('.');
} if (i == 8) printf("\n(x)");
putchar('\n');
} putchar('\n');
for (int i = 0; i < 3; i++, putchar('\n'))//输出全局
for (int j = 0; j < 3; j++)
if (filled[i][j] == now) putchar('X');
else if (filled[i][j]) putchar('O');
else putchar('.');
}
inline bool can_step(pii pos, pii id) {
if (pos.first < 0 || pos.first > 8 || pos.second < 0 || pos.second > 8) return false;
return board[pos.first][pos.second] == 0 && (make_pair(pos.first / 3, pos.second / 3) == id || id == make_pair(-1, -1));
}
inline void rev() {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) board[i][j] = -board[i][j];
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) filled[i][j] = -filled[i][j];
}
inline void do_fill(pii id) {
int sx = id.first * 3, sy = id.second * 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) board[sx + i][sy + j] = 1;
filled[id.first][id.second] = 1;
}
inline void try_fill(pii id) {
if (filled[id.first][id.second] != 0) return;
int sx = id.first * 3, sy = id.second * 3;
for (int i = 0; i < 3; i++) {
bool flag = true;
for (int j = 0; j < 3; j++) {
int x = sx + i, y = sy + j;
if (board[x][y] != 1) {
flag = false;
break;
}
}
if (flag) {
do_fill(id);
return;
}
}
for (int j = 0; j < 3; j++) {
bool flag = true;
for (int i = 0; i < 3; i++) {
int x = sx + i, y = sy + j;
if (board[x][y] != 1) {
flag = false;
break;
}
}
if (flag) {
do_fill(id);
return;
}
}
bool flag = true;
for (int i = 0; i < 3; i++) {
int x = sx + i, y = sy + i;
if (board[x][y] != 1) {
flag = false;
break;
}
}
if (flag) {
do_fill(id);
return;
}
flag = true;
for (int i = 0; i < 3; i++) {
int x = sx + i, y = sy + (2 - i);
if (board[x][y] != 1) {
flag = false;
break;
}
}
if (flag) {
do_fill(id);
return;
}
}
inline bool gameover() {
for (int i = 0; i < 3; i++) {
bool flag = true;
for (int j = 0; j < 3; j++) {
if (filled[i][j] != 1) {
flag = false;
break;
}
}
if (flag) return true;
}
for (int j = 0; j < 3; j++) {
bool flag = true;
for (int i = 0; i < 3; i++) {
if (filled[i][j] != 1) {
flag = false;
break;
}
}
if (flag) return true;
}
bool flag = true;
for (int i = 0; i < 3; i++)
if (filled[i][i] != 1) {
flag = false;
break;
}
if (flag) return true;
flag = true;
for (int i = 0; i < 3; i++)
if (filled[i][2 - i] != 1) {
flag = false;
break;
}
if (flag) return true;
return false;
}
char lis[18][6] = {"", "wza", "hyh", "frz", "wyr", "wby", "zhr", "czh", "gch", "zmr", "yjr", "lzy", "wjw", "xzw", "x r", "g l", "rand", "qyzy"};
pii init(int &waiting_time) {
int a[3];
for (int i = 1; i <= 2; i++) {
printf("please input a number from 1 to 17 to choose the bot for the player %c, or you will play it yourself: ", i == 1 ? 'X' : 'O');
cin >> a[i];
while (a[i] == 114514) {
printf("list:\n");
for (int i = 1; i <= 17; i++) {
printf("%2d %s\n", i, lis[i]);
}
printf("%2d yourself\n", 18);
printf("please input a number from 1 to 17 to choose the bot for the player %c, or you will play it yourself: ", i == 1 ? 'X' : 'O');
cin >> a[i];
}
}
if (1 <= a[1] && a[1] <= 17 && 1 <= a[2] && a[2] <= 17) {
printf("you have chose two bots. please input a number(ms) in order to let them chess slower(ms): ");
cin >> waiting_time;
}
return make_pair(1 <= a[1] && a[1] <= 17 ? a[1] : 18, 1 <= a[2] && a[2] <= 17 ? a[2] : 18);
}
inline pii get_step(int ch, pii id, const vector<vector<int> > &board) {
switch (ch) {
case 1:
return WZA::step(id, board);
case 2:
return HYH::step(id, board);
case 3:
return HBY::step(id, board);
case 4:
return GL::step(id, board);
case 5:
return WYR::step(id, board);
case 6:
return ZHR::step(id, board);
case 7:
return CZH::step(id, board);
case 8:
return GCH::step(id, board);
case 9:
return ZMR::step(id, board);
case 10:
return YJR::step(id, board);
case 11:
return LZY::step(id, board);
case 12:
return WJW::step(id, board);
case 13:
return XZW::step(id, board);
case 14:
return XR::step(id, board);
case 15:
return FRZ::step(id, board);
case 16:
return QYZY::step(id, board);
case 17:
return Rand::step(id, board);
case 18:
return Human::step(id, board);
}
}
inline void Game() {
pii lst = { -1, -1};
board.resize(9);
for (int i = 0; i < 9; i++) board[i].resize(9);
for (int i = 0, j; i < 9; i++) for (j = 0; j < 9; j++)board[i][j] = 0;
memset(filled, 0, sizeof filled);
int T = 0, waiting_time = 100;
pii chose = init(waiting_time);
long long Time[3][50], time_sum[2] = {0}, time_begin;
while (++T) {
for (int i = 1; i <= 2; i++) {
system("cls"), printf("Round #%d\n", T);
print_board(board, i == 1 ? 1 : -1);
printf("\nplayer %c go\n", i == 1 ? 'X' : 'O');
time_begin = clock();
Time[i][T] = clock();
pii st = get_step(i == 1 ? chose.first : chose.second, trans(lst), board);
Time[i][T] = clock() - Time[i][T];
time_sum[1] += Time[1][T], time_sum[2] += Time[2][T];
if (i > 1) {
puts ("/*Players think about time in this round*/"), printf("X : %dms ; O : %dms\n", Time[1][T], Time[2][T]);
puts ("/*Total thinking time*/"), printf("X : %dms ; O : %dms\n", time_sum[1], time_sum[2]);
} if (!can_step(st, trans(lst))) {
puts("unlaw"), cout << st.first << ' ' << st.second << '\n';
printf("player %c lose!\n", i == 1 ? 'X' : 'O');
printf("press any key to quit...");
getchar(), getchar();
return;
} else {
board[st.first][st.second] = 1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) try_fill(make_pair(i, j));
}
rev();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) try_fill(make_pair(i, j));
}
rev();
if (gameover()) {
system("cls");
puts ("/*Total thinking time*/"), printf("X : %dms ; O : %dms\n", time_sum[1], time_sum[2]);
printf("player %c won!\n", i == 1 ? 'X' : 'O');
print_board(board, i == 1 ? 1 : -1);
printf("\npress any key to quit..");
getchar(), getchar();
return;
}
}
if (T >= 13) {
bool flag = true;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) {
flag = false;
break;
}
}
}
if (flag) {
system("cls"), printf("NIE\nthe board is full!\n");
puts ("/*Players think about time in this round*/"), printf("X : %dms ; O : %dms\n", Time[1][T], Time[2][T]);
puts ("/*Total thinking time*/"), printf("X : %dms ; O : %dms\n", time_sum[1], time_sum[2]);
print_board(board, i == 1 ? 1 : -1);
printf("\npress any key to quit..");
getchar(), getchar();
return;
}
} lst = st, rev(), Sleep(waiting_time);
}
}
}
int Round;
int main() {
printf("How many rounds are you gonna play?");
cin >> Round;
while(Round--) system("cls"), Game();
return 0;
}