https://codeforces.com/gym/100917/problem/A
題目大意:給出一個 n ∗ n n*n n∗n的圖形,字母 a − z a-z a−z表示不同的顔色,字元 ? ? ?表示任意顔色均可,初始 n ∗ n n*n n∗n的圖形是麼得顔色的,你每次可以把某一行或某一列染成相同的顔色,輸出一個染色方案使得按照這個方案染色可以得出給定的圖形(染色方案為 2 n 2n 2n行,每一行和每一列均要被染色過)。
思路:不考慮 ? ? ?字元,如果某一行(列)隻有一種顔色,根據貪心思想這一行(列)放在最後染色肯定是最優的,我們可以用隊列存儲,那麼在這之前它們被染成什麼顔色都是無關緊要的,是以可以把這一行(列)的字元全部修改成 ? ? ?,然後再判斷有沒有新的行(列)滿足上述條件,如果滿足則将其繼續加入隊列,直到所有的行和列都計算到了。答案就是進隊序列的逆序。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=10005;
struct node
{
char tag,ch;
int id;
node(){}
node(char tt,int i,char c)
{
tag=tt,id=i,ch=c;
}
}ans[maxn];
bool vis[maxn];
int rcnt[maxn][30];
int ccnt[maxn][30];
int rnum[maxn],cnum[maxn];
char s[maxn][maxn];
queue<int> q;
int n,len;
char getch(int id)
{
if(id<=n)
{
if(rnum[id]==0)
return 'a';
for(int i=0;i<26;i++)
if(rcnt[id][i])
return i+'a';
}
else
{
if(cnum[id]==0)
return 'a';
for(int i=0;i<26;i++)
if(ccnt[id][i])
return i+'a';
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j]!='?')
{
if(!rcnt[i][s[i][j]-'a'])
{
++rnum[i];
++rcnt[i][s[i][j]-'a'];
}
else
++rcnt[i][s[i][j]-'a'];
if(!ccnt[j+n][s[i][j]-'a'])
{
++cnum[j+n];
++ccnt[j+n][s[i][j]-'a'];
}
else
++ccnt[j+n][s[i][j]-'a'];
}
}
}
for(int i=1;i<=n;i++)
{
if(rnum[i]<=1)
q.push(i),vis[i]=1,ans[++len]=node('h',i,getch(i));
if(cnum[i+n]<=1)
q.push(i+n),vis[i+n]=1,ans[++len]=node('v',i,getch(i+n));
}
int tmp;
while(!q.empty())
{
tmp=q.front();
q.pop();
if(tmp<=n) //行
{
for(int i=1;i<=n;i++)
{
if(s[tmp][i]=='?'||vis[i+n])
continue;
if(--ccnt[i+n][s[tmp][i]-'a']==0)
{
if(--cnum[i+n]==1)
{
ans[++len]=node('v',i,getch(i+n));
vis[i+n]=1;
q.push(i+n);
}
}
s[tmp][i]='?';
}
}
else //列
{
tmp-=n;
for(int i=1;i<=n;i++)
{
if(s[i][tmp]=='?'||vis[i])
continue;
if(--rcnt[i][s[i][tmp]-'a']==0)
{
if(--rnum[i]==1)
{
ans[++len]=node('h',i,getch(i));
vis[i]=1;
q.push(i);
}
}
s[i][tmp]='?';
}
}
}
for(int i=len;i>=1;i--)
printf("%c %d %c\n",ans[i].tag,ans[i].id,ans[i].ch);
return 0;
}