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

· · 题解

这道题真心难搞，细节比较多，对于像我这样的蒟蒻，代码基础不是很好，生生调了一个下午才搞对，这道题我们看到题目给出的条件说：

矩形的边的宽度为 1 ，每条边的长度都不小于 3 。

矩形的每条边中，至少有一部分是可见的。注意，一个角同时属于两条边。

矩形用大写字母表示，并且每个矩形的表示符号都不相同。

这样的话我们可以首先预处理搞出每个矩形的左上角和右下角，然后扫描矩形的每一条边，遇到不是本矩形自身的字母，我们就加一条边s[i][j]，表示i被j覆盖，这样搞完后，我们直接跑拓扑排序就好，但是我们要处理处每种可能的情况，所以我们要用dfs而不是for循环了，在网上学习了一下拓扑排序，没想到就是楼下的，好巧啊，但是预处理等其他的并没有抄袭，大家可以借鉴一下（蒟蒻连拓扑排序都不会555~）这个拓扑排序算是写的很好的了，（题解才两篇，管理员大人帮忙过下）

/*****

> Author: Drinkwater-cnyali
> Created Time: 2017/5/6 14:44:08

****/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
int read()
{
    int sum = 0, fg = 1; char c = getchar();
    while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * fg;
}
const int maxn = 100000;
const int inf = 0x3f3f3f3f;
int n,m;
char Map[40][40];
struct node { int x,y;};node M[40][2];
void init()
{
    REP(i,1,31)
    {
        REP(l,1,31)
            REP(r,1,31)
                M[i][0].x = -inf,M[i][0].y = -inf;
        REP(l,1,31)
            REP(r,1,31)
                M[i][1].x = inf,M[i][1].y = inf;
    }
}
int id[40],cnt,vis[40],s[40][40],deg[40],ans[40],ff;
map<string,bool>mp;
vector<string> as;
void topsort(int x,string now)
{
    if(x > cnt && !mp[now])
    {
        mp[now] = 1;
        as.push_back(now);
        return ;
    }
    REP(i,1,cnt)
    {
        if(!deg[id[i]] && !vis[id[i]])
        {
            vis[id[i]] = 1;
            deg[id[i]] = -1;
            REP(j,1,cnt)
                if(s[id[i]][id[j]])
                    deg[id[j]]--;
            topsort(x+1,now+char(id[i]+'A'-1));
            REP(j,1,cnt)
                if(s[id[i]][id[j]])
                    deg[id[j]]++;
            deg[id[i]] = 0,vis[id[i]] = 0;
        }
    }
}
int main()
{
    n = read(), m = read();
    init();
    for(int i = 1; i <= n; i++)
    {
        scanf("%s",Map[i]);
        int Len = strlen(Map[i]);
        for(int j = 0; j < Len;++j)
        {
            if(Map[i][j] == '.')continue;
            int T = Map[i][j] - 'A' +1;
            if(!vis[T])id[++cnt] = T,vis[T] = 1;
            M[T][0].x = max(M[T][0].x,i);
            M[T][0].y = max(M[T][0].y,j);
            M[T][1].x = min(M[T][1].x,i);
            M[T][1].y = min(M[T][1].y,j);
        }
    }
    /*REP(i,1,cnt)
    {
        int T = id[i];
        cout<<T<<endl;
        cout<<M[T][0].x<<" "<<M[T][0].y+1<<endl;
        cout<<M[T][1].x<<" "<<M[T][1].y+1<<endl;
        cout<<"~~~~"<<endl;
    }*/memset(s,0,sizeof(s));
    REP(k,1,cnt)
    {
        int T = id[k],c;
        int Mx = M[T][1].x,My = M[T][1].y,Fx = M[T][0].x,Fy = M[T][0].y;
        REP(i,Mx,Fx)
        {
            if(Map[i][My] != '.')
            {
                c = Map[i][My]-'A'+1;
                if(!s[T][c] && T != c)s[T][c] = 1,deg[c]++;
            }
            if(Map[i][Fy] != '.')
            {
                c = Map[i][Fy]-'A'+1;
                if(!s[T][c] && T != c)s[T][c] = 1,deg[c]++;
            }
        }
        REP(i,My,Fy)
        {
            if(Map[Mx][i]!='.')
            {
                c = Map[Mx][i]-'A'+1;
                if(!s[T][c] && T != c)s[T][c] = 1,deg[c]++;
            }
            if(Map[Fx][i]!='.')
            {
                c = Map[Fx][i]-'A'+1;
                if(!s[T][c] && T != c)s[T][c] = 1,deg[c]++;
            }
        }
    }
    /*REP(i,1,cnt)
    {
        cout<<"!!!"<<id[i]<<endl;
        REP(j,1,cnt)if(s[id[i]][id[j]])cout<<id[j]<<" ";
        cout<<endl;
    }*/
    memset(vis,0,sizeof(vis));
    topsort(1,"");
    sort(as.begin(),as.end());
    REP(i,0,as.size()-1)
        cout<<as[i]<<endl;
    return 0;
}