CF1863D

题面

Link

There is an $n\times m$ board divided into cells. There are also some dominoes on this board. Each domino covers two adjacent cells (that is, two cells that share a side), and no two dominoes overlap.

Piet thinks that this board is too boring and it needs to be painted. He will paint the cells of the dominoes black and white. He calls the painting beautiful if all of the following conditions hold:

• for each domino, one of its cells is painted white and the other is painted black;
• for each row, the number of black cells in this row equals the number of white cells in this row;
• for each column, the number of black cells in this column equals the number of white cells in this column.

Note that the cells that are not covered by dominoes are not painted at all, they are counted as neither black nor white.

Help Piet produce a beautiful painting or tell that it is impossible.

思路

事先说明：对于覆盖区域为 LR 的骨牌，称为水平骨牌，对于覆盖区域为 UD 的骨牌，称为竖直骨牌。

首先可以发现，水平骨牌在某一行内无论怎么分配都不会使这一行不合法，所以对于水平骨牌我们只需要考虑它所在的列（一个水平骨牌会横跨两列）。假如某一列中有 $x$ 个水平骨牌，如果 $x$ 是奇数那么就一定无解，否则就按照一半骨牌为黑白一半骨牌为白黑的方向放置，顺序无所谓，对于每一列均是如此。

对于竖直骨牌我们同样只考虑它所在的行（一个竖直骨牌横跨两行），与列的情况相同，这里不多赘述，直接上代码。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 505;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        char s[N][N], ans[N][N];
        int ver[N], hor[N];
        memset(ver, 0, sizeof(ver));
        memset(hor, 0, sizeof(hor));
        memset(ans, '.', sizeof(ans));
        for(int i = 0; i < n; i++)
            scanf("%s", s[i]);
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(s[i][j] == 'U')
                {
                    ver[i]++;
                }
                else if(s[i][j] == 'L')
                {
                    hor[j]++;
                }
            }
        }
        bool bj = false;
        for(int i = 0; i < n; i++)
        {
            int cnt = 0;
            if(ver[i] & 1)
            {
                bj = true;
                cout << -1 << endl;
                break;
            }
            for(int j = 0; j < m; j++)
            {
                if(s[i][j] == 'U')
                {
                    cnt++;
                    if(cnt <= (ver[i] >> 1))
                    {
                        ans[i][j] = 'B';
                        ans[i + 1][j] = 'W';
                    }
                    else
                    {
                        ans[i][j] = 'W';
                        ans[i + 1][j] = 'B';
                    }
                }
            }
        }
        for(int i = 0; i < m; i++)
        {
            int cnt = 0;
            if((hor[i] & 1) && !bj)
            {
                bj = true;
                cout << -1 << endl;
                break;
            }
            for(int j = 0; j < n; j++)
            {
                if(s[j][i] == 'L')
                {
                    cnt++;
                    if(cnt <= (hor[i] >> 1))
                    {
                        ans[j][i] = 'B';
                        ans[j][i + 1] = 'W';
                    }
                    else
                    {
                        ans[j][i] = 'W';
                        ans[j][i + 1] = 'B';
                    }
                }
            }
        }
        if(bj) continue;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
                printf("%c", ans[i][j]);
            puts("");
        }
    }
    return 0;
}