CF1503B 题解

2021-04-04 12:22:36


题目大意

这是一道交互题。

你需要和交互库玩一个游戏。交互库每次给出一个属于 $[1,3]$ 的整数,你需要在一个 $n\times n$ 的网格图中任意一个格子上填写一个属于 $[1,3]$ 且和交互库给出的整数不同的整数。

如果任意时刻网格图中相邻两个格子(有公共边)上的数相同,你就输了,否则你就赢了。

你需要赢得这个游戏。

换位思考

如果你是交互库,你打算怎么玩?

其实容易想到,如果网格图中出现任意一个空的格子,其四周中的格子里中有不同的数,那么你一直给出没有出现过的那个数,到最后你就赢了。

举个例子,如果一个空的格子,其上方格子中填了 $1$,右方格子填了 $2$,那么你只要一直给出 $3$,对手就一直没法填这个空格子。

想到这里就差不多了。

解题

我们为了避免上面那种情况,可以考虑交错着填,填到最后达到这种状态:

或这种状态:

其中同一张图中黄色格子中填的数字是一样的,白色格子可填可不填,但填的数字不能和黄色格子中数字一样。

这样,剩余的空格子就可以很轻松填完了(因为不论交互库给出什么整数,剩余的任意一个空格子总有至少一种数字可填)。

具体实现的时候,如下图。为了达到上面那两种状态之一,我们可以规定红色格子填一个固定值,黄色格子填另一种固定值,如果交互库给出的数等于红色格子中的值,那么就填黄色格子,否则就填红色格子。最终,总有一种颜色的格子被先填满,也就是到达上面两种状态之一。

代码实现

代码中,我是斜着填的,当然这样写太麻烦了,容易出错,可以横着填,竖着填。

#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;
            }
        }
    }
}