CF1503B 题解
t162
2021-04-04 12:22:36
## 题目大意
这是一道交互题。
你需要和交互库玩一个游戏。交互库每次给出一个属于 $[1,3]$ 的整数，你需要在一个 $n\times n$ 的网格图中任意一个格子上填写一个属于 $[1,3]$ 且和交互库给出的整数不同的整数。
如果任意时刻网格图中相邻两个格子（有公共边）上的数相同，你就输了，否则你就赢了。
你需要赢得这个游戏。
## 换位思考
如果你是交互库，你打算怎么玩？
其实容易想到，如果网格图中出现任意一个空的格子，其四周中的格子里中有不同的数，那么你一直给出没有出现过的那个数，到最后你就赢了。
举个例子，如果一个空的格子，其上方格子中填了 $1$，右方格子填了 $2$，那么你只要一直给出 $3$，对手就一直没法填这个空格子。
想到这里就差不多了。
## 解题
我们为了避免上面那种情况，可以考虑交错着填，填到最后达到这种状态：
或这种状态：
其中同一张图中黄色格子中填的数字是一样的，白色格子可填可不填，但填的数字不能和黄色格子中数字一样。
这样，剩余的空格子就可以很轻松填完了（因为不论交互库给出什么整数，剩余的任意一个空格子总有至少一种数字可填）。
具体实现的时候，如下图。为了达到上面那两种状态之一，我们可以规定红色格子填一个固定值，黄色格子填另一种固定值，如果交互库给出的数等于红色格子中的值，那么就填黄色格子，否则就填红色格子。最终，总有一种颜色的格子被先填满，也就是到达上面两种状态之一。
## 代码实现
代码中，我是斜着填的，当然这样写太麻烦了，容易出错，可以横着填，竖着填。
```cpp
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<limits>
namespace StandardLibrary {
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::fixed;
using std::flush;
using std::setprecision;
using std::setw;
using std::numeric_limits;
}
using namespace StandardLibrary;
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector>
namespace STL {
using std::bitset;
using std::complex;
using std::deque;
using std::greater;
using std::less;
using std::map;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::stack;
using std::string;
using std::vector;
using std::make_pair;
using std::sort;
}
using namespace STL;
#define rep(var, start, end) for(int var = (start), var##_end = (end); var <= var##_end; var++)
#define rrep(var, start, end) for(int var = (start), var##_end = (end); var >= var##_end; var--)
namespace IO {
template <typename T>
inline T read(T& dest) {
int c = getchar(); T f = 1; dest = 0;
while (c < 48 || c > 57) f *= (c == 45 ? -1 : 1), c = getchar();
while (c >= 48 && c <= 57) dest = (dest << 3) + (dest << 1) + (c ^ 48), c = getchar();
return dest *= f;
}
template <typename T, typename... args>
inline void read(T& dest, args&... dests) { read(dest), read(dests...); }
template <typename T>
inline T read() {
int c = getchar(); T f = 1, dest = 0;
while (c < 48 || c > 57) f *= (c == 45 ? -1 : 1), c = getchar();
while (c >= 48 && c <= 57) dest = (dest << 3) + (dest << 1) + (c ^ 48), c = getchar();
return dest * f;
}
template <typename T>
inline void put(T val) {
T tmp = 0, l = 0; if (val < 0) putchar('-'), val = -val;
while (val) tmp = tmp * 10 + (val % 10), l++, val /= 10;
if (l == 0) putchar('0');
else {
while (l) putchar((tmp % 10) + 48), l--, tmp /= 10;
while (l) putchar('0'), l--;
}
}
template <>
inline void put<char*>(char* val) { rep(i, 0, ((int)strlen(val)) - 1) putchar(val[i]); }
template <>
inline void put<const char*>(const char* val) {
rep(i, 0, ((int)strlen(val)) - 1) putchar(val[i]);
}
template <>
inline void put<string>(string val) { put(val.c_str()); }
template <typename T, typename... args>
inline void put(T val, args&... values) { put(val), putchar(' '), put(values...); }
template <typename T>
inline void write(T val) {
put(val), putchar(' ');
}
template <typename T, typename... args>
inline void write(T val, args&... values) { write(val), write(values...); }
inline void writeln() { puts(""); }
template <typename T>
inline void writeln(T val) { put(val), writeln(); }
template <typename T, typename... args>
inline void writeln(T val, args&... values) { put(val), putchar(' '), writeln(values...); }
}
using namespace IO;
namespace Tools {
template <typename T, typename... args>
inline void log(T val) { cerr<<val<<endl; }
template <typename T, typename... args>
inline void log(T val, args... lists) { cerr<<val<<' '; log(lists...); }
}
using namespace Tools;
//=======正文开始=======
int a[201][201];
int n, k, oi = 1, oj = 1, ei = 2, ej = 1, flag = 1, li = 1, lj = 1;
void _put(int b, int i, int j) { a[i][j] = b, writeln(b,i,j), fflush(stdout); } //填充函数
int main() {
read(n);
for (int i = 1; i <= n * n; i++) {
int d; read(d);
if (k == 0) { //确定两种格子颜色
if (d == 1) {
_put(2, 1, 1), k = 2, oi++, oj++;
} else _put(1, 1, 1), k = 1, oi++, oj++;
} else if (flag) { //未达到两种状态
if (d == k) {
_put(3 - k, ei, ej);
ei++, ej++;
if (ei > n) ei -= n, ej -= (n & 1);
if (ej > n) ej -= n, ei -= (n & 1);
if (a[ei][ej]) {
if (ei == n || ei == n - 1) flag = 0;
else ei += 2;
}
} else {
_put(k, oi, oj);
oi++, oj++;
if (oi == oj && oi > n) oi -= n, oj -= n;
if (oi > n) oi -= n, oj += (n & 1);
if (oj > n) oj -= n, oi += (n & 1);
if (a[oi][oj]) {
if (oi == n || oi == n - 1) flag = 0;
else oi += 2;
}
}
} else { //达到两种状态之一
int f = 0;
for (; li <= n; li++) {
if (lj == n + 1) lj = 1;
for (; lj <= n; lj++) {
if (a[li][lj]) continue;
if ((li >= lj && (li - lj) % 2 == 1) || ((li < lj) && (lj - li) % 2 == 1)) {
if (3 - k == d) _put(3, li, lj);
else _put(3 - k, li, lj);
} else {
if (d == k) _put(3, li, lj);
else _put(k, li, lj);
}
f = 1; break;
}
if (f) break;
}
}
}
}
```