题解 P2741 【[USACO4.4]重叠的图像Frame Up】
interestingLSY
2017-11-26 19:46:33
#爆搜即可
###原因
题目中说“矩形的每条边中,至少有一部分是可见的。注意,一个角同时属于两条边。“
这就意味着我们可以通过记录同一个矩形中字母的最大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;
}
```