根据题意，每个矩形总能找到他的四个角的坐标，先找出各个矩形，再遍历每个矩形的四条边，例如：若在遍历矩形A的四条边时候，遇到B。
则图中存在边A->B
如此建立边的关系之后即刻拓扑排序。最后对结果进行排序。
PS：结果数量比较大。
/**//*
ID: lorelei3
TASK: frameup
LANG: C++
*/
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXL = 30;
const int MAXA = 10000;
struct Rect
{
char letter;
int xmin, xmax, ymin, ymax;
};
struct Sequeue{
char strs[MAXL];
bool operator < (const Sequeue &seq)const {
int re = strcmp(strs, seq.strs);
if(re<0)
return true;
else
return false;
}
};
ifstream fin("frameup.in");
ofstream fout("frameup.out");
Rect rect[MAXL];
Sequeue ans[MAXA];
int acnt, len;
char board[MAXL][MAXL];
bool map[MAXL][MAXL], visited[MAXL], used[MAXL];
int n,m,l;
inline int min(int a, int b){
return a<b? a:b;
}
inline int max(int a, int b){
return a>b? a: b;
}
void input(){
int i,j,k;
fin>>n>>m;
for(i=0; i<n; ++i){
for(j=0; j<m; ++j){
char ch;
fin>>ch;
board[i][j]=ch;
if(ch=='.')
continue;
k = ch-'A';
if(k>len) len=k;
if(!used[k]){
l++;
used[k]=true;
rect[k].letter=ch;
rect[k].xmax = i, rect[k].xmin = i, rect[k].ymax = j, rect[k].ymin = j;
}else{
rect[k].xmax = max(rect[k].xmax, i);
rect[k].xmin = min(rect[k].xmin, i);
rect[k].ymax = max(rect[k].ymax, j);
rect[k].ymin = min(rect[k].ymin, j);
}
}
fin.get();
}
for(k=0; k<MAXL; ++k){
if(used[k]){
for(int x=rect[k].xmin, y1=rect[k].ymin, y2=rect[k].ymax; x<=rect[k].xmax; ++x){
int p1 = board[x][y1] - 'A';
if(k!=p1)
map[k][p1]=true;
int p2 = board[x][y2] - 'A';
if(k!=p2)
map[k][p2]=true;
}
for(int y=rect[k].ymin, x1=rect[k].xmin, x2=rect[k].xmax; y<=rect[k].ymax; ++y){
int p1 = board[x1][y] - 'A';
if(k!=p1)
map[k][p1]=true;
int p2 = board[x2][y] - 'A';
if(k!=p2)
map[k][p2]=true;
}
}
}
}
char tmp[30];
bool hasprefix(int u){
for(int i=0; i<=len; ++i){
if(!used[i]) continue;
if(map[i][u] && !visited[i])
return true;
}
return false;
}
void topsort(int u, int k){
if(k==l){
strcpy(ans[acnt++].strs, tmp);
return;
}
else{
visited[u]=true;
for(int i=0; i<=len; ++i){
if(!used[i])
continue;
if(!visited[i] && !hasprefix(i)){
tmp[k]=rect[i].letter;
topsort(i, k+1);
}
}
visited[u]=false;
}
}
void solve(){
for(int i=0; i<=len; ++i){
if(used[i] && !hasprefix(i)){
tmp[0] = rect[i].letter;
topsort(i, 1);
}
}
}
void output(){
sort(ans, ans+acnt);
for(int i=0; i<acnt; ++i)
fout<<ans[i].strs<<endl;
}
int main(){
input();
solve();
output();
return 0;
}posted on 2011-02-04 16:48
小阮 阅读(355)
评论(0) 编辑 收藏 引用 所属分类:
USACO