原题链接：https://codeforces.com/gym/105161/problem/D

题目大意

给定一个 n 行 n 列 (3\leq n\leq 100) 的网格，从上到下，从左到右将行列依次编号为 1 到 n，初始每个单元格中的值均为 −1。你需要给单元格赋值，每轮你可以选择一个单元格，考虑与其四连通（上下左右）的单元格（不包括你选择的单元格）中的值组成的集合 S，则你可以将这个单元格重新赋值为 [0,mex(S)] 中的一个整数，一个格子可以多次进行赋值操作。请构造一种赋值方案，使得最后值为 3 的单元格数不少于 \lfloor \frac{2(n-1)^2}{3}\rfloor 个。

思路

由于题目不要求操作次数最少，且恒有 mex(S)\geq 0 ，因此为了方便起见，可以首先把所有格子初始化为0。
我们需要尽可能的增加 3 的数量，且在创建新的 3 的过程中不能破坏原先已有的 3。

一个 3 可以由下所示的最小单元内创建（由此可见，角落位置不可能创建出 3 ）：

通过这个最小单元，可以比较容易的得到一种方案，即在每一行（第 n 行除外）上，奇数行通过方式 A，偶数行通过方式 B，每隔 2 格创建一个 3：

这样可以创建出 \lfloor \frac{n(n-1)}{2}\rfloor 个 3。当 n\leq 5 时，这种方案是能满足题设的，但随着 n 的增大，这种方案就不再可行了。
为了能创建出 \lfloor \frac{2(n-1)^2}{3}\rfloor 个 3，我们可以考虑将第 i 行除了 (i, n) 以外的格子全部填满（其中 i 可以被 3 整除，且 i \neq n ）：

在剩下的格子里，再仿造上一种方案创建 3：

这种方案可以保证至少能够创建出 \lfloor \frac{2(n-1)^2}{3}\rfloor 个 3。

之后通过代码模拟上述过程即可。

以下为史山代码：

#include <bits/stdc++.h>
#define CNO cout << "NO\n"
#define CYES cout << "YES\n"
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef __int128 i128;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int n;
ll ans = 0;
string str;
struct Arr {
  int x, y, num;
};
vector<Arr> v;

void op(int x, int y, int num) {
  v.push_back({x, y, num});
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  while (T--) {
    v.clear();
    cin >> n;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        op(i, j, 0);
      }
    }
    for (int i = 3; i < n; i += 3) {
      for (int j = 1; j < n; ++j) {
        op(i, j, 1);
        op(i, j + 1, 2);
        op(i - 1, j, 1);
        op(i, j, 3);
        op(i - 1, j, 0);
      }
      op(i, n, 0);
    }
    for (int i = 1; i < n; i += 3) {
      for (int j = n; j > 1; --j) {
        if (j == n) {
          if (i == 1) {
            op(i + 1, j, 1);
            op(i + 1, j - 1, 2);
            op(i, j, 1);
            op(i + 1, j, 3);
            op(i, j, 0);
            op(i + 1, j - 1, 0);
          } else {
            op(i, j, 1);
            op(i, j - 1, 2);
            op(i + 1, j, 1);
            op(i, j, 3);
            op(i + 1, j, 0);
            op(i, j - 1, 0);
          }
        } else {
          if ((n - j + (i == 1)) % 2) {
            op(i + 1, j, 1);
            op(i, j, 2);
            op(i + 1, j - 1, 1);
            op(i + 1, j, 3);
            op(i + 1, j - 1, 0);
            op(i, j, 0);
          } else {
            op(i, j, 1);
            op(i + 1, j, 2);
            op(i, j - 1, 1);
            op(i, j, 3);
            op(i, j - 1, 0);
            op(i + 1, j, 0);
          }
          if (n % 3 == 0 && i + 2 == n && (n - j + (i == 1)) % 2 == 0) {
            i++;
            op(i + 1, j, 1);
            op(i, j, 2);
            op(i + 1, j - 1, 1);
            op(i + 1, j, 3);
            op(i + 1, j - 1, 0);
            op(i, j, 0);
            i--;
          }
        }
      }
    }
    cout << v.size() << endl;
    for (auto i : v) cout << i.x << ' ' << i.y << ' ' << i.num << endl;
  }
  return 0;
}