# interestingLSY 的博客

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

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

# 爆搜即可

### 细节

-消除矩形：把要消除的矩形各边都设成空白（就是"."）即可

### 优化

（但其实爆搜就挺快了，才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();
}
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);

for( int i = 1 ; i <= n ; i++ ){
for( int j = 1 ; j <= m ; j++ ){
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;
}