题解 P2741 【[USACO4.4]重叠的图像Frame Up】

· · 题解

这道题是我在USACO里面用时最久的一道好了不废话了

这一道题正解是拓扑，但是我觉得拓扑比暴力更好打。。。。

思路：

因为“矩形的每条边中，至少有一部分是可见的”，所以我们只

需要根据边来找出矩形的左上角和右上角

然后搜索每一个矩阵，如果这个矩阵被别的矩阵覆盖了，就与

另外一个矩阵建立一条边，然后拓扑一次就好了

注：没有被连接的矩形才是最底的（当前），这样可以省去很

的步骤

代码如下：

#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
struct node
{
    int x,y,next;
}a[5100];int len,last[51];//边，表示要先用了这一个矩阵才能用下一个矩阵 
int s[51];//表示有多少个矩阵在这一个点的上面 
struct node1
{
    int x1,y1;
    int x2,y2;
    node1()
    {
        x1=y1=100;
    }
}g[51];//记录左上和右下 
inline void ins(int x,int y)//建边 
{
    len++;
    a[len].x=x;a[len].y=y;s[y]++;
    a[len].next=last[x];last[x]=len;
}
int n,m,length,d[51];//length表示出现的矩阵的次数，d为编目录优化，这个还挺有用的 
int f[51][51];//地图 
bool v[51];//这种型号的矩阵是否有 
inline void find(int k)//查找为k的矩阵 
{
    bool bk[51];memset(bk,true,sizeof(bk));//记录那种矩形是否被找过，如果找过了，就没有必要多建边了 
    for(int j=g[k].y1;j<=g[k].y2;j++)//先找上下 
    {
        if(f[g[k].x1][j]!=k && bk[f[g[k].x1][j]]==true) 
        {
            ins(k,f[g[k].x1][j]);
            bk[f[g[k].x1][j]]=false;
        }
        if(f[g[k].x2][j]!=k && bk[f[g[k].x2][j]]==true) 
        {
            ins(k,f[g[k].x2][j]);
            bk[f[g[k].x2][j]]=false;
        }
    }
    for(int i=g[k].x1;i<=g[k].x2;i++) //再找左右 
    {
        if(f[i][g[k].y1]!=k && bk[f[i][g[k].y1]]==true) 
        {
            ins(k,f[i][g[k].y1]);
            bk[f[i][g[k].y1]]=false;
        }
        if(f[i][g[k].y2]!=k && bk[f[i][g[k].y2]]==true) 
        {
            ins(k,f[i][g[k].y2]);
            bk[f[i][g[k].y2]]=false;
        }
    }
}
int b[51];//记录拓扑时的队列 
inline void tuopu(int x,int t)//删边或者回溯 
{
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        s[y]+=t;
    }
}
void dfs(int k)//拓扑排序，k表示现在队列里有k-1个 
{
    if(k==length+1)//如果到达了 
    {
        for(int i=1;i<k;i++) printf("%c",b[i]+'A'-1);//变为字符串然后输出 
        printf("\n");return;
    }
    for(int i=1;i<=length;i++)//枚举 
    {
        if(v[d[i]]==true)//如果没有被找过 
        {
            if(s[d[i]]==0)//如果地下没有矩形了 
            {
                v[d[i]]=false;
                b[k]=d[i];//记录 
                tuopu(d[i],-1);//伪删边 
                dfs(k+1);//往下搜索 
                v[d[i]]=true;//回溯 
                b[k]=0;
                tuopu(d[i],1);
            }
        }
    }
}
inline int cmp(const void *xx,const void *yy)//排序 
{
    int x=*(int*)xx;
    int y=*(int*)yy;
    if(x>y) return 1;
    if(x<y) return -1;
    return 0;
}
int main()
{
    char st[51];int i,j;
    scanf("%d%d",&n,&m);
    memset(v,false,sizeof(v));
    for(i=1;i<=n;i++)
    {
        scanf("%s",st+1);
        for(j=1;j<=m;j++)
        {
            if(st[j]=='.') continue;//不用管没有的 
            f[i][j]=st[j]-'A'+1;
            if(v[f[i][j]]==false)
            {
                v[f[i][j]]=true;
                length++;d[length]=f[i][j];
            }
            g[f[i][j]].x1=min(g[f[i][j]].x1,i);//记录左上角和右下角 
            g[f[i][j]].y1=min(g[f[i][j]].y1,j); 
            g[f[i][j]].x2=max(g[f[i][j]].x2,i);
            g[f[i][j]].y2=max(g[f[i][j]].y2,j);
        }
    }
    qsort(d+1,length,sizeof(int),cmp);//记得排序目录 
    for(i=1;i<=length;i++)//找一次 
    {
        find(d[i]);
    }
    dfs(1);//拓扑排序 
    return 0;
}