P10361 Łamigłówka 3 题解

· · 题解

P10361 题解

提供一种比较奇怪的解法？

Analysis

观察题面，不难发现可以反推来进行模拟。例如样例：

假设我们最后一行填充了第三列，那么反向删除它：

注意到第一行、第三行、第四行分别出现了四个 A。由于我们下一步即将填充第三列，所以第三行的颜色无关紧要，我们可以将他们涂成 A，这样颜色就符合要求了。只要这一行或列只有一种颜色或者其他的格子无法确定（即下一次涂色马上涂掉），那么我们可以将这一行或列放入下一次扩展的序列，并且下次扩展的时候再次寻找这样的行或列。这样操作直到所有格子全部覆盖到，操作就结束。我们可以倒序输出我们模拟的序列。

Solution

刚才说到，我们需要记录每一行的字母。对于扩展序列，我们可以使用队列存放操作来进行扩展。需要注意的是这里扩展情况可以直接改动而且不需要回溯，因为同时扩展的多个状态是并发的，操作先后并不影响。每次读入状态我们直接把他放到答案栈序列中。由于我们并不需要最小化答案，所以操作 n+m 次也是合法的。

注意到如果我们暴力寻找每一行、列的字母是否只有一种，那么每次扩展需要搜索 n\times m 个格子，然而操作步数最多来到 n + m 次，这样的时间复杂度无法接受。我们可以记录每一行、列的对应字母个数，由于至多只有 26 个字母，因此我们可以直接建立二维数组记录每行或列的字母个数和删除行或列的次数。例如搜索到一行：当该行对应一种字母（例如 A）的个数 S_A、已经修改的列数 D、总行数 n 满足 n-D=S_A 时，这行就全部是 A 字母了。

另外，当我们涂掉这行或者列时，对应的字母数量也要更改。

还有很多细节，还是看代码吧，马蜂不良仅供参考。

Code

#include <bits/stdc++.h>
using namespace std;
struct node{; //{type,value,color} type=0 行 type=1 列 value 行/列号
    int type;
    int b;
    int color;
};
stack <node> ans;//答案栈序列
int mp[2005][2005];
int hc[2005][30];//每行的字母个数
int lc[2005][30];//每列的字母个数
bool mh[2005],ml[20005];//分别标记行、列是否被操作过
int ht,lt;
int cnt;
int n,m;
queue <node> q;
string s;
int main(){
    cin>>n>>m;
    for (int i = 1;i<=n;i++){
        cin>>s;
        for (int j = 0;j<m;j++){
            mp[i][j+1]=s[j]-'A';
            hc[i][s[j]-'A']++;
            lc[j+1][s[j]-'A']++;
        }
    }
    q.push({2,114514,1919810});
    while (!q.empty()){
        node cur=q.front();
        q.pop();
        //删除
        if (cur.type==0){
            for (int i = 1;i<=m;i++){
                if (mp[cur.b][i]!=cur.color) continue;
                lc[i][cur.color]--;
            }
            lt++;
        }
        else if(cur.type==1){
            for (int i = 1;i<=n;i++){
                if (mp[i][cur.b]!=cur.color)continue;
                hc[i][cur.color]--;
            }
            ht++;
        }
        //扩展
        for (int i = 1;i<=n;i++){
            for (int j = 0;j<27;j++){
                if (hc[i][j]==m-ht&&mh[i]==false&&m!=ht){
                    mh[i]=true;
                    q.push({0,i,j});
                }
            }
        }
        for (int i = 1;i<=m;i++){
            for (int j = 0;j<27;j++){
                if (lc[i][j]==n-lt&&ml[i]==false&&n!=lt){
                    ml[i]=true;
                    q.push({1,i,j});
                }
            }
        }
        ans.push(cur);
    }
    cout<<ans.size()-1<<endl;
    while (!ans.empty()){
        node cur=ans.top();
        ans.pop();
        if (cur.type==0){
            char col=cur.color+'A';
            cout<<"R"<<" "<<cur.b<<" "<<col<<endl;
        }
        else if(cur.type==1){
            char col=cur.color+'A';
            cout<<"K"<<" "<<cur.b<<" "<<col<<endl;
        }
    }
    return 0;
}