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

vinvor · 2017-09-01 23:48:18 · 题解

拓扑排序

由题意可知，不存在一个矩形的一条边被完全覆盖，所以我们可以计算出矩形的坐标。读入时记录矩形的每个点中最小x1，最小y1，最大x2，最大y2。可知左上角(x1，y1)右下角(x2，y2)右上角(x2，y1)左下角(x1，y2)。查找该矩形A边上，非该矩形的字母B，即覆盖矩形A被矩形B覆盖。建立一条有向边B->A，表示B是A的必要条件。然后进行拓扑排序，搜索求所有的拓扑序列，并排序输出。

注意，该题中的字母可能不连续，不要直接for(i='A';i<='Z';i++)。

字符串处理

每次找到一个完全框（也就是这个框的所有字母都可见，要么是原来的字母，要么是“*”，“*”是后面用到的临时标记），拿掉，把框上的所有字母都标记为“*”。重复上述过程直到所有框都被拿掉。因为要求输出所有答案，所以用dfs来寻找所有解。

下附代码：

#include<bits/stdc++.h> 
#define rep(i, n) for(int i = 1; i <= n;i++)
using namespace std;
int w, h, p, l[50], r[50], u[50], d[50], D[50];
char mapp[50][50], _p[50];
bool a[50], g[50][50];
void dfs(){
    bool flag = 0;
    rep(i, 26)
        if(a[i]){
            flag = 1;
            break;
        }
    if(!flag){
        rep(i, p)
            printf("%c", _p[i]);
        printf("\n");
        return;
    }
    rep(i, 26)
        if(a[i] && D[i] == 0){
                _p[++p] = i + '@';
                rep(j, 26)
                    if(g[i][j])
                        D[j]--;
                a[i] = 0;
                dfs();
                rep(j, 26)
                    if(g[i][j])
                        D[j]++;
                a[i] = 1;
                p--;
        }
}
int main(){
    ios::sync_with_stdio(false);
    scanf("%d%d", &w, &h);
    rep(i, w){
        scanf("\n");
        rep(j, h){
            char c = getchar();
            mapp[i][j] = c;
            if(!l[c - '@'] || j < l[c - '@'])
                l[c - '@'] = j;
            if(!r[c - '@'] || j > r[c - '@'])
                r[c - '@'] = j;
            if(!u[c - '@'] || i < u[c - '@'])
                u[c - '@'] = i;
            if(!d[c - '@'] || i > d[c - '@'])
                d[c - '@'] = i;
            a[c - '@'] = 1;
        }
    }
    memset(g, 0, sizeof(g));
    rep(i, 26)
        if(a[i]){
            for(int j = l[i]; j <= r[i]; j++){
                if(mapp[u[i]][j] != '.')
                    g[i][mapp[u[i]][j] - '@'] = 1;
                if(mapp[d[i]][j] != '.')
                    g[i][mapp[d[i]][j] - '@'] = 1;
            }
            for(int j = u[i]; j <= d[i]; j++){
                if(mapp[j][l[i]] != '.')
                    g[i][mapp[j][l[i]] - '@'] = 1;
                if(mapp[j][r[i]] != '.')
                    g[i][mapp[j][r[i]] - '@'] = 1;
            }
        }
    rep(i, 26)
        rep(j, 26)
            if(i != j && g[i][j])
                D[j]++;
    p = 0;
    dfs();
    return 0;
}