题解 P2741 【[USACO4.4]重叠的图像Frame Up】
这道题好难啊
对于我这个小蒟蒻来说
这道题，明显就是个拓扑 我觉得爆搜的都是巨佬
删除线用上瘾了
好，进入正题。这道拓扑题首先是要建边。因为他说每一条边都至少有一个。所以我们只要找出一个个矩阵的边界，这非常好找，然后开始建边。建边就是枚举每一个矩形，发现“有外员侵入”的就建一条边。比如
AAABBBA
A..B.BA
AAABBBA此时，A矩阵的边界为上：1 下：3 左：1 右：7
B矩阵的边界同理懒
然后就枚举A矩阵，发现有B“侵入”，就A->b建一条边
边建好了，接下来就是拓扑。 由于他说不只一个情况，所以我们要去深搜。深搜就是把队列里面每一个入度为0的都拿出来跑一遍，而不是每次取头跑了。把每一次的答案记下来，sort一下就好了。
代码（你们最喜欢的）
#include<bits/stdc++.h>
using namespace std;
char a[31][31];
const int N=500001;
struct data{
int x1=1e9,x2,y1=1e9,y2;
}x[27];
int node[N],head[N],nxt[N],into[N],zf,cnt,b[N],ans[N],bb[N],q[N],r,hh=1;
string ans2[N];
void add(int x,int y)
{
node[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
void dfs(int dep)
{
if(dep>zf)
{
for(int i=zf;i>=1;i--){
char c=ans[i]+'A'-1;
ans2[hh]+=c;
}
hh++;
return;
}
for(int i=1;i<=r;i++)
{
if(b[i]==0)
{
int rr=r;
int x=q[i];
for(int j=head[x];j;j=nxt[j])
{
into[node[j]]--;
if(into[node[j]]==0)q[++r]=node[j];
}
b[i]=1;
ans[dep]=x;
dfs(dep+1);
b[i]=0;
for(int j=head[x];j;j=nxt[j])into[node[j]]++;
r=rr;
}
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]!='.')
{
int h=(int)(a[i][j]-'A'+1);
if(bb[h]==0)zf++;
bb[h]=1;
if(i<x[h].x1)x[h].x1=i;
if(i>x[h].x2)x[h].x2=i;
if(j<x[h].y1)x[h].y1=j;
if(j>x[h].y2)x[h].y2=j;
}
}
for(int i=1;i<=26;i++)
{
if(x[i].x1!=0){
for(int j=x[i].x1;j<=x[i].x2;j++)
{
int h=a[j][x[i].y1]-'A'+1;
if(h!=i)add(h,i),into[i]++;
h=a[j][x[i].y2]-'A'+1;
if(h!=i)add(h,i),into[i]++;
}
for(int j=x[i].y1;j<=x[i].y2;j++)
{
int h=a[x[i].x1][j]-'A'+1;
if(h!=i)add(h,i),into[i]++;
h=a[x[i].x2][j]-'A'+1;
if(h!=i)add(h,i),into[i]++;
}
}
}
for(int i=1;i<=26;i++)
if(bb[i]==1&&into[i]==0)q[++r]=i;
dfs(1);
sort(ans2+1,ans2+hh);
for(int i=1;i<=hh-1;i++)
{
for(int j=0;j<zf;j++)printf("%c",ans2[i][j]);
printf("\n")；
}
}为什么我的码风上了这里就变得鬼畜了
好，没了