3-Coloring
C++ 代码
/*
我们将矩阵分成两部分,对于 (i, j),如果 i + j 是奇数,我们将它看作黑色格子,否则将他看作白色格子,
这样我们可以发现任意一个所有黑色格子一定互不相邻,白色格子也是。
然后我们先尝试填 1 和 2,我们将 1 填入白色格子,将 2 填入黑色格子,那么考虑什么时候我们无法再继续填了,
由于 Alice 也是最优决策,因此当白色格子和黑色格子中某一边填完了,这里假设白色格子填完了,那么只要 Alice
选择 2,那么我们在剩下的黑子格子中填 1 一定会冲突。此时由于剩下的黑色格子一定是互不相邻的,只要我们不
往黑色格子中填 1,就一定不会冲突,因此我们接下来就用 2 和 3 继续填剩下的黑色格子。按照这个思路如果黑色格子
先被填完也是同理。
通过上述思路我们得出以下:
如果 Alice 选 1,如果黑色格子有空,就在黑色格子上填 2,否则就在白色格子上填 3
如果 Alice 选 2,如果白色格子有空,就在白色格子上填 1,否则就在黑色格子上填 3
如果 Alice 选 3,如果白色格子有空,就在白色格子上填 1,否则就在黑泽格子上填 2
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
void work()
{
int n;
scanf("%d", &n);
vector<PII> black, white;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i + j & 1) black.push_back({i, j});
else white.push_back({i, j});
for(int i = 0; i < n * n; i++)
{
int a;
scanf("%d", &a);
if(a == 1)
{
if(black.size())
printf("%d %d %d\n", 2, black.back().first, black.back().second), black.pop_back();
else
printf("%d %d %d\n", 3, white.back().first, white.back().second), white.pop_back();
}
else if(a == 2)
{
if(white.size())
printf("%d %d %d\n", 1, white.back().first, white.back().second), white.pop_back();
else
printf("%d %d %d\n", 3, black.back().first, black.back().second), black.pop_back();
}
else
{
if(white.size())
printf("%d %d %d\n", 1, white.back().first, white.back().second), white.pop_back();
else
printf("%d %d %d\n", 2, black.back().first, black.back().second), black.pop_back();
}
fflush(stdout);
}
}
int main()
{
work();
return 0;
}