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

interestingLSY

2017-11-26 19:46:33

Solution

#爆搜即可 ###原因 题目中说“矩形的每条边中,至少有一部分是可见的。注意,一个角同时属于两条边。“ 这就意味着我们可以通过记录同一个矩形中字母的最大x坐标、最大y坐标、最小x坐标、最小y坐标来获得矩形的左下角和右上角的坐标 接着,由题意我们可知符合的方案可能不只有一个,所以可以dfs(bfs也行) ###实现 每次dfs时,寻找当前“完整”的矩形(“完整”是指矩形的各条边都没有被其它还没被消除的矩形挡住),然后去掉这个矩形,继续递归 ###细节 -消除矩形:把要消除的矩形各边都设成空白(就是".")即可 ###优化 我们可以使用拓扑排序,然后在图上跑dfs,这样就能更快的AC了 (但其实爆搜就挺快了,才44ms) ###代码 ```cpp #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; } ```