interestingLSY 的博客

interestingLSY 的博客

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

posted on 2017-11-26 19:46:33 | under 题解 |

爆搜即可

原因

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

这就意味着我们可以通过记录同一个矩形中字母的最大x坐标、最大y坐标、最小x坐标、最小y坐标来获得矩形的左下角和右上角的坐标

接着,由题意我们可知符合的方案可能不只有一个,所以可以dfs(bfs也行)

实现

每次dfs时,寻找当前“完整”的矩形(“完整”是指矩形的各条边都没有被其它还没被消除的矩形挡住),然后去掉这个矩形,继续递归

细节

-消除矩形:把要消除的矩形各边都设成空白(就是".")即可

优化

我们可以使用拓扑排序,然后在图上跑dfs,这样就能更快的AC了

(但其实爆搜就挺快了,才44ms)

代码

#include <bits/stdc++.h>
#define INF ((int)(1e9))
#define LINF ((ll)(1e18))
#define pb push_back
#define mp make_pair
#define ll long long
#define _tp template
#define _tyn typename
#define ull unsigned ll
#define pii pair<int,int>
#define uint unsigned int
#define ms(_data) memset(_data,0,sizeof(_data))
#define fin(_filename) freopen(_filename,"r",stdin)
#define fout(_filename) freopen(_filename,"w",stdout)
#define msn(_data,_num) memset(_data,_num,sizeof(_data))
using namespace std;
_tp<_tyn T>void mymax( T &_a , T _b ){ if( _a < _b ) _a = _b; }
_tp<_tyn T>void mymin( T &_a , T _b ){ if( _a > _b ) _a = _b; }
int getnum(){
    char ch = '.';
    int fu = 1;
    while( ch < '0'  ||  ch > '9' ){
        ch = getchar();
        if( ch == '-' ) fu = -1;
    }
    int ret = 0;
    while( ch >= '0'  &&  ch <= '9' ){
        ret = ret * 10 + (ch-'0');
        ch = getchar();
    }
    return ret;
}
char getlet(){
    char ch = '%';
    while( ( ch < 'A'  ||  ch > 'Z' )  &&  ch != '.' ) ch = getchar();
    return ch;
}
void read( int &x, int &y ){
    x = getnum(); y = getnum();
}
void read( char &c ){
    c = getlet();
}
/////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////
#define MAXN 40
struct Pos{
    int y,x;
    Pos(){}
    Pos( int yy , int xx ){
        y = yy;
        x = xx;
    }
};
int n,m;
int data[MAXN][MAXN];
Pos ld[MAXN],ur[MAXN];
bool exist[MAXN];

//检测一个矩形是否完整
bool test( int x ){
    for( int i = ld[x].x ; i <= ur[x].x ; i++ ){
        if( data[ld[x].y][i] != x  &&  data[ld[x].y][i] != -1 ) return 0;
        if( data[ur[x].y][i] != x  &&  data[ur[x].y][i] != -1 ) return 0;
    }
    for( int i = ur[x].y ; i <= ld[x].y ; i++ ){
        if( data[i][ld[x].x] != x  &&  data[i][ld[x].x] != -1 ) return 0;
        if( data[i][ur[x].x] != x  &&  data[i][ur[x].x] != -1 ) return 0;
    }
    return 1;
}
//消除一个矩形
void seton( int x , int a ){
    for( int i = ld[x].x ; i <= ur[x].x ; i++ ){
        data[ld[x].y][i] = a;
        data[ur[x].y][i] = a;
    }
    for( int i = ur[x].y ; i <= ld[x].y ; i++ ){
        data[i][ld[x].x] = a;
        data[i][ur[x].x] = a;
    }
}

vector<string> ans;
void dfs( string now ){
    bool gao = 0;
    for( int i = 0 ; i < 26 ; i++ ){
        if( !exist[i] ) continue;
        if( !test(i) ) continue;
        gao = 1;
        exist[i] = 0;
        int ls[MAXN][MAXN];
        memcpy(ls,data,sizeof(ls));
        seton(i,-1);
        dfs( now + (char)(i+'A') );
        memcpy(data,ls,sizeof(data));
        exist[i] = 1;
    }
    if( gao ) return;
    reverse(now.begin(),now.end());
    ans.pb(now);
}
int main(){
    //fin("frameup.in");
    //fout("frameup.out");
    for( int i = 0 ; i < 26 ; i++ ){
        ld[i].y = 0; ld[i].x = INF;
        ur[i].y = INF; ur[i].x = 0;
    }
    msn(data,-1);
    ms(exist);

    read(n,m);
    for( int i = 1 ; i <= n ; i++ ){
        for( int j = 1 ; j <= m ; j++ ){
            char c; read(c);
            if( c == '.' ) continue;
            data[i][j] = c-'A';
            exist[data[i][j]] = 1;
                       //记录矩形左下角、右上角坐标
            mymax( ld[data[i][j]].y , i );
            mymin( ld[data[i][j]].x , j );
            mymin( ur[data[i][j]].y , i );
            mymax( ur[data[i][j]].x , j );
        }
    }

    dfs("");

        //整理答案
    sort(ans.begin(),ans.end());
    for( uint i = 0 ; i < ans.size() ; i++ )
        cout << ans[i] << endl;

    return 0;
}