Two-Colored Dominoes 题解

前言

看了这道题的几篇题解，感觉讲的方法都比较麻烦，这里讲一个感觉比较简单的方法。

思路

首先判断是否有解。计算一下每一行和每一列的牌的数量，只要有一个是奇数就无解，否则有解。证明显然，偶数一定可以分成两组，在纸上模拟一下也可以得出。

其次看如何构造。对于竖着的牌，显然只对每行有影响，因为列上的颜色一定是一黑一白的。所以我们就只需要按照行来枚举竖着的牌，每一行上依次按照 \(0101...\) 这样的顺序去构造就可以了。需要注意的是，我们只用构造每张牌的上面的那个点，因为下面的点可以通过上面的点的颜色计算出来。

横着的牌按照相同方法构造就可以了。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define re register
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 1e3 + 10;
int T,n,m,ans[MAXN][MAXN],len_l[MAXN],len_r[MAXN];
char c[MAXN][MAXN];
signed main()
{
	cin >> T;
	while(T--)
	{
		int flag = false,tmp = 2;
		cin >> n >> m;
		for(int i = 1;i <= n;i++) len_l[i] = 0;
		for(int i = 1;i <= m;i++) len_r[i] = 0;
		for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) ans[i][j] = 2;
		for(int i = 1;i <= n;i++) 
			for(int j = 1;j <= m;j++) 
			{
				cin >> c[i][j];
				if(c[i][j] != '.') len_l[i]++,len_r[j]++;
				else ans[i][j] = 1;
			}
		for(int i = 1;i <= n;i++) if(len_l[i] % 2) flag = true;
		for(int i = 1;i <= m;i++) if(len_r[i] % 2) flag = true;
		if(flag == true){puts("-1");continue;}
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= m;j++)
				if(c[i][j] == 'U') ans[i][j] = tmp,ans[i + 1][j] = tmp ^ 1,tmp ^= 1;
		for(int j = 1;j <= m;j++)
			for(int i = 1;i <= n;i++)
				if(c[i][j] == 'L') ans[i][j] = tmp,ans[i][j + 1] = tmp ^ 1,tmp ^= 1;
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= m;j++)
			{
				if(ans[i][j] == 1) cout << '.';
				if(ans[i][j] == 2) cout << 'B';
				if(ans[i][j] == 3) cout << 'W'; 
			}	
			cout << endl;
		}
			
	}
	return 0;
}