codeforces gym 100917 Abstract Picture 贪心+思维(正难反易)

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