题解：P11476 [COCI 2024/2025 #3] 涂矩阵 / Bojanje

· · 题解

题意

我们有一个 n\times n 的全 0 矩阵，现在我们希望用一些将某一行或某一列全部染成 2,3 的操作使其变成目标矩阵并构造方案或输出无解。

思路

我们某一行或者某一列一定不会被染色多次，因此操作次数小于等于 4\times 10^3 显然是满足的。我们发现，当我们的当前矩阵有某一行或者某一列均为同一种颜色时，我们显然可以在末尾添加一次操作将这行或列染色掉，然后便可以将这一行或列直接在当前矩阵中删除掉。由于我们是倒序加入操作的，所以并不需要考虑对其它操作的影响。

考虑我们这样一直将可以染色的行或列全部删除直到没有可删除的行或列了该怎么办。我们发现，如果此时还有没有被染色正确的点的话就一定无解了。为什么呢，我们发现，此时无论如何染某一行或列，都一定会有不满足最终矩阵的位置。因此我们只需要一直操作到不能继续操作，再按照找到的操作还原矩阵判断一下与最终矩阵相不相同即可。

代码

#include<bits/stdc++.h>
#define N 2000 + 39
using namespace std;
int a[N][N], h[3][N], l[3][N], n, c[N][N];
bool vis[2][N];
struct Node
{
    int op, x, color;
};
stack<Node>ans, check;
queue<Node>q;
int main()
{
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            cin >> a[i][j];
            h[a[i][j]][i] ++;
            l[a[i][j]][j] ++;//我们记录每一行每一列0，1，2的个数，这样就能快速找到全1或2的行或列
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        if(h[0][i])//有0一定不能染色
        {
            vis[0][i] = 1;//判断一行或一列能否被染色，有0的显然不行
        }
        else
        {
            if(!h[1][i])
            {
                vis[0][i] = 1;
                q.push({1, i, 2});
            }
            else if(!h[2][i])
            {
                vis[0][i] = 1;
                q.push({1, i, 1});
            }
        }
        if(l[0][i])
        {
            vis[1][i] = 1;
        }
        else
        {
            if(!l[1][i])
            {
                vis[1][i] = 1;
                q.push({2, i, 2}); 
            }
            else if(!l[2][i])
            {
                vis[1][i] = 1;
                q.push({2, i, 1});
            }
        }
    }
    while(q.size())//一直寻找可以被操作的位置
    {
        check.push(q.front());
        ans.push(q.front());
        int op = q.front().op, x = q.front().x, color = q.front().color;
        q.pop();
        if(op == 1)
        {
            for(int i = 1; i <= n; i ++)
            {
                if(vis[1][i])
                {
                    continue;
                }
                l[color][i] --;//修改行的时候更新每一列
                if(l[color][i] == 0)
                {
                    vis[1][i] = 1;
                    q.push({2, i, color == 1 ? 2 : 1});
                }
            }
        }
        else
        {
            for(int i = 1; i <= n; i ++)
            {
                if(vis[0][i])
                {
                    continue;
                }
                h[color][i] --;//同理
                if(h[color][i] == 0)
                {
                    vis[0][i] = 1;
                    q.push({1, i, color == 1 ? 2 : 1});
                }
            }
        }
    }
    while(check.size())//还原一下我们的操作的最终矩阵
    {
        int op = check.top().op, x = check.top().x, color = check.top().color;
        check.pop();
        for(int i = 1; i <= n; i ++)
        {
            if(op == 1)
            {
                c[x][i] = color;
            }
            else
            {
                c[i][x] = color;
            }
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(c[i][j] != a[i][j])
            {
                cout << -1;//不合法输出-1
                return 0;
            }
        }
    }
    cout << ans.size() << '\n';
    while(ans.size())
    {
        cout << ans.top().op << ' ' << ans.top().x << ' ' << ans.top().color << '\n';
        ans.pop();
    }
    return 0;
}

AC 记录。