随笔-141  评论-9  文章-3  trackbacks-0
根据题意,每个矩形总能找到他的四个角的坐标,先找出各个矩形,再遍历每个矩形的四条边,例如:若在遍历矩形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 小阮 阅读(350) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理