CF1863D Two-Colored Dominoes 题解
Links
Description
有一个 \(n \times m\) 的棋盘，上面铺着一些 \(1 \times 2\) 的多米诺骨牌（横竖均有可能），骨牌之间没有重叠。
你需要找到一种染色方案满足以下条件：
- 每个多米诺骨牌一端被染白，另一端被染黑。其他没有骨牌的格子不染色。
- 对于棋盘的每一行，被染黑的格子数等于被染白的格子数。
- 对于棋盘的每一列，被染黑的格子数等于被染白的格子数。
请输出任意一种染色方案，如果无解，输出 \(-1\)。
本题有多组测试数据，\(1 \leq T \leq 10^{4}\)，\(2 \leq n,m \leq 500\)，\(\sum (n \times m) \leq 2.5 \times 10^{5}\)。
Solution
由于题目限制每个多米诺骨牌一端被染白，另一端被染黑，因此容易得出 横着摆放的骨牌对行的限制没有影响，横着摆放的骨牌对列的限制没有影响。
因此我们可以先看行的限制，显然，如果一行中有奇数个竖着放的骨牌则无解。
然后分类讨论：
- 若当前格子是骨牌的上侧，没有限制，但要考虑后面的格子。
- 若当前格子是骨牌的下侧，由于上一行已经遍历过，当前格子的状态就已经确定了。
因此我们可以记录三个数字，\(cnt_{1}\) 表示没有限制的格子数量，\(cnt_{2}\) 表示一定需要染黑的数量，\(cnt_{3}\) 表示一定需要染白的数量。
统计结束后，对于每个没有限制的格子，我们贪心的选择当前少的颜色涂，数量相同的时候随便选一个就行，这样到最后如果两个颜色数量还不同就无解了。
列的限制同理即可。
时间复杂度 \(\Omicron \left( n \times m\right)\)。
Codes
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read(int &p)
{
p = 0;
int k = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
{
k = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9')
{
p = p * 10 + c - '0';
c = getchar();
}
p *= k;
return;
}
void write_(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
write_(x / 10);
}
putchar(x % 10 + '0');
}
void writesp(int x)
{
write_(x);
putchar(' ');
}
void writeln(int x)
{
write_(x);
putchar('\n');
}
int T;
int n,m;
char mp[510][510],ans[510][510];
void solution()
{
read(n),read(m);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
ans[i][j] = '.';
}
}
for(int i = 1;i <= n;i++)
{
scanf("%s",mp[i] + 1);
}
// 是否有答案；
bool flag = true;
// 先考虑行的情况，由于横着的不会造成影响直接跳过
for(int i = 1,cnt1,cnt2,cnt3;i <= n;i++)
{
// cnt1 无法确定个数
// cnt2 确定的 B
// cnt3 确定的 W
cnt1 = cnt2 = cnt3 = 0;
for(int j = 1;j <= m;j++)
{
if(mp[i][j] == 'U')
{
++cnt1;
}
else if(mp[i][j] == 'D')
{
if(ans[i - 1][j] == 'W')
{
++cnt2;
}
else
{
++cnt3;
}
}
}
if((cnt1 + cnt2 + cnt3) & 1)
{
flag = false;
break;
}
else
{
for(int j = 1;j <= m;j++)
{
if(mp[i][j] == 'U')
{
if(cnt2 > cnt3)
{
ans[i][j] = 'W';
++cnt3;
}
else
{
ans[i][j] = 'B';
++cnt2;
}
}
else if(mp[i][j] == 'D')
{
if(ans[i - 1][j] == 'W')
{
ans[i][j] = 'B';
}
else
{
ans[i][j] = 'W';
}
}
}
}
if(cnt2 != cnt3) {
flag = false;
}
}
for(int j = 1,cnt1,cnt2,cnt3;j <= m;j++) {
cnt1 = cnt2 = cnt3 = 0;
for(int i = 1;i <= n;i++) {
if(mp[i][j] == 'L') {
++cnt1;
}
else if(mp[i][j] == 'R') {
if(ans[i][j - 1] == 'W') {
++cnt2;
}
else {
++cnt3;
}
}
}
if((cnt1 + cnt2 + cnt3) & 1) {
flag = false;
break;
}
else {
for(int i = 1;i <= n;i++) {
if(mp[i][j] == 'L') {
if(cnt2 > cnt3) {
ans[i][j] = 'W';
++cnt3;
}
else {
ans[i][j] = 'B';
++cnt2;
}
}
else if(mp[i][j] == 'R') {
if(ans[i][j - 1] == 'W'){
ans[i][j] = 'B';
}
else{
ans[i][j] = 'W';
}
}
}
}
if(cnt2 != cnt3){
flag = false;
}
}
if(flag == false){
puts("-1");
return ;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
putchar(ans[i][j]);
ans[i][j] = '.';
}
puts("");
}
}
signed main()
{
read(T);
while(T--){solution();}
return 0;
}