CF1863D Two-Colored Dominoes 题解

Links

洛谷

Codeforces

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