自动搬运

查看原文

来自洛谷，原作者为

	pzc2004 Прекрасное далёко, не будь ко мне жестоко

搬运于2025-08-24 21:41:03，当前版本为作者最后更新于2019-08-05 19:12:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

这题在NOIP2018前几天被我们教练拿来当PJ信心赛的T3

思路很容易想到，因为每个矩形的每条边都有一部分露出来，所以只需要记录下每种字母的x、y坐标的最大值、最小值即可确定每个矩形，然后就可以推出哪些字母覆盖了哪些字母。

然后就是怎么找情况了，一开始我选择最暴力的方法，枚举所有排列，如果不满足字母覆盖关系就退出。

代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int jx[26][4],ss;//jx记录每个矩形的四个角，ss记录字母的种数
bool b[26][26];//b[i][j]表示字母j覆盖了字母i
bool bbb[26];//bbb[i]表示字母i是否出现过
void dfs(string s)
{
	if(s.size()==ss){cout<<s<<endl;return;}//如果枚举完了就输出
	for(int i=0;i<26;i++)//枚举每种字母
	{
		if(!bbb[i])continue;//如果字母i没出现过就continue
		bool bb=1;
		for(int j=0;j<s.size();j++)
		{
			if(b[i][s[j]-'A']){bb=0;break;}//如果不满足覆盖关系就退出
		}
		if(bb){bbb[i]=0;dfs(s+char(i+'A'));bbb[i]=1;}//如果满足覆盖关系就往下dfs
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	string s[n];
	for(int i=0;i<n;i++)cin>>s[i];
	for(int k=0;k<26;k++)jx[k][1]=jx[k][3]=999;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i][j]!='.')
			{
				int kkk=s[i][j]-'A';
				bbb[kkk]=1;
				jx[kkk][0]=max(jx[kkk][0],i);//记录每个矩形的四角
				jx[kkk][1]=min(jx[kkk][1],i);
				jx[kkk][2]=max(jx[kkk][2],j);
				jx[kkk][3]=min(jx[kkk][3],j);
			}
		}
	}
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<26;k++)if(bbb[k] && (((i==jx[k][0] || i==jx[k][1]) && j<=jx[k][2] && j>=jx[k][3]) || ((j==jx[k][2] || j==jx[k][3]) && i<=jx[k][0] && i>=jx[k][1])))b[k][s[i][j]-'A']=1;//记录覆盖关系
	for(int i=0;i<26;i++)if(bbb[i])ss++;
	dfs("");
}

结果最后一个点悲惨TLE。

然后改变思路，因为已知哪个字母在哪个字母下面，可以想到使用拓扑排序，于是便AC了。

代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int jx[26][4],ss,kkk,n,m,rd[26];//变量都一样,rd[i]表示字母i的入度
bool b[26][26],bbb[26];
char sss[26];
inline void dfs(int l)//拓扑排序（懒得改函数名了）
{
    if(l==ss){printf("%s\n",sss);return;}
    for(register int i=0;i<26;++i)
    {
        if(!bbb[i])continue;//如果字母i没出现过就continue
        if(rd[i]==0)//如果字母i的入度等于0就进行拓扑排序
        {
        	for(register int j=0;j<26;j++)
        	{
        		if(b[i][j])rd[j]--;//将所有覆盖当前字母的入度减1
			}
			sss[l]=i+'A';
			bbb[i]=0;
        	dfs(l+1);//往下dfs
        	bbb[i]=1;
        	for(register int j=0;j<26;j++)
        	{
        		if(b[i][j])rd[j]++;//进行还原
			}
		}
    }
}
int main()//都一样
{
    int i,j,k;
    scanf("%d%d\n",&n,&m);
    char s[n][m];
    for(i=0;i<n;++i)scanf("%s",s[i]);
    for(k=0;k<26;++k)jx[k][1]=jx[k][3]=999;
    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
        {
            if(s[i][j]!='.')
            {
                kkk=s[i][j]-'A';
                bbb[kkk]=1;
                jx[kkk][0]=max(jx[kkk][0],i);
                jx[kkk][1]=min(jx[kkk][1],i);
                jx[kkk][2]=max(jx[kkk][2],j);
                jx[kkk][3]=min(jx[kkk][3],j);
            }
        }
    }
    for(i=0;i<n;++i)for(j=0;j<m;++j)for(k=0;k<26;++k)if(k!=s[i][j]-'A' && !b[k][s[i][j]-'A'] && bbb[k] && (((i==jx[k][0] || i==jx[k][1]) && j<=jx[k][2] && j>=jx[k][3]) || ((j==jx[k][2] || j==jx[k][3]) && i<=jx[k][0] && i>=jx[k][1])))
	{b[k][s[i][j]-'A']=1;rd[s[i][j]-'A']++;}//如果字母k在字母s[i][j]-'A'下面就将字母s[i][j]-'A'的入度加1
    for(i=0;i<26;++i)if(bbb[i])++ss;
    dfs(0);
}