/*
ID: wangzha4
LANG: C++
TASK: frameup
*/
//JUDGE_ID: 65448BI
/*
Test 1: TEST OK [0.000 secs, 3312 KB]
Test 2: TEST OK [0.000 secs, 3312 KB]
Test 3: TEST OK [0.011 secs, 3312 KB]
Test 4: TEST OK [0.000 secs, 3308 KB]
Test 5: TEST OK [0.000 secs, 3444 KB]
Test 6: TEST OK [0.000 secs, 3308 KB]
Test 7: TEST OK [0.000 secs, 3308 KB]
Test 8: TEST OK [0.011 secs, 3440 KB]
Test 9: TEST OK [0.043 secs, 3440 KB]
*/
//拓撲排序的題目－－輸出所有可能的拓撲排序－－按字典序
/*
具體思路 :
1. 讀入數據，用used[]記錄那些字符被使用過，并將字符hash到
從小到大的數字cnt,用mymap[]數組來將數字hash回相應的字符
2. 尋找矩形框－－找到每種字符最大和最小的行列,存放在node[]數組中
3. 構建圖形edge[][]--掃描輸入,對于每個字母,按照矩形框掃描四個邊
如果掃描到不相同的字母，建立一條有向邊，edge[][]=1
4. DFS_Topsort()--對于已經建立好的有向邊利用深度優先搜索排序
5. 輸出所有的拓撲序列
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define unllong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
typedef long long llong ;
//const double PI = 2.0 * acos( 0.0 ) ；
const int Base=1000000000;
const int Capacity=100;
const int INF = 1000000 ;
const int size = 35 ;
struct NODE
{
int minr, minc ;
int maxr, maxc ;
};
struct NODE node[28] ;
char data[size][size] ;
int used[200] ;//把字符映射成數字
char mymap[200] ;//把數字映射成字符
int cnt ;//記錄映射的最大數字--圖的最大頂點標號
int edge[30][30] ;//構建有向圖
int indeg[30] ;//記錄所有的點的入度
int row, col ;
char topout[30] ;//暫存生成的拓撲序列
struct OUT
{
char str[30] ;
};
struct OUT out[20000] ;
int ct_out ;
int fmax( int a, int b )
{
if( a > b ) return a ;
else return b ;
}
int fmin( int a, int b )
{
if( a < b ) return a ;
else return b ;
}
void input()
{
memset( used, 0, sizeof(used) ) ;
memset( mymap, 0, sizeof(mymap) ) ;
memset( indeg, 0, sizeof(indeg) ) ;
memset( edge, 0, sizeof(edge) ) ;
cnt = 1 ;
for( int i=0; i<row; i++ ) {
scanf( "%s", data[i] ) ;
for( int j=0; j<col; j++ ) {
if( '.' == data[i][j] ) continue ;
if( used[data[i][j]] ) continue ;
used[data[i][j]] = cnt ; mymap[cnt++] = data[i][j] ;
}//建立相互映射
}
for( int i=0; i<=26; i++ ) {
node[i].minr = node[i].minc = INF ;
node[i].maxr = node[i].maxc = -1 ;
}//初始化每個字母的最小最大行列
}
void find_degree()
{
for( int i=1; i<cnt; i++ )
for( int j=1; j<cnt; j++ )
indeg[i] += edge[j][i] ;
}
void DFS_Topsort( int sn, int tdep )
{
int back[30] ;//深搜的用于暫存狀態的數組
for( int i=1; i<cnt; i++ ) back[i] = indeg[i] ;
if( sn == tdep )
{
//printf( "=======%s\n", topout ) ;
strcpy( out[ct_out].str, topout ) ;
ct_out++ ;
return ;
}
for( int i=1; i<cnt; i++ )
{
if( 0 == indeg[i] ) {
topout[sn] = mymap[i] ; indeg[i] = -1 ;
for( int k=1; k<cnt; k++ )
if( edge[i][k] ) indeg[k]-- ;//入度減1
DFS_Topsort( sn+1, tdep ) ;
for( int k=1; k<cnt; k++ ) indeg[k] = back[k] ;
}
}
}
void find_edge( int curn )
{//對四個邊進行查找－－尋找矩形框
int minr = node[curn].minr ; int minc = node[curn].minc ;
int maxr = node[curn].maxr ; int maxc = node[curn].maxc ;
int nodex, nodey ; nodey = used[curn+'A'] ;
for( int k=minc; k<=maxc; k++ )
{
if( data[minr][k]!='.'&&data[minr][k]!=curn+'A' ) {
nodex = used[data[minr][k]] ; edge[nodey][nodex] = 1 ;
}
if( data[maxr][k]!='.'&&data[maxr][k]!=curn+'A' ) {
nodex = used[data[maxr][k]] ; edge[nodey][nodex] = 1 ;
}
}
for( int k=minr; k<=maxr; k++ )
{
if( data[k][minc]!='.'&&data[k][minc]!=curn+'A' ) {
nodex = used[data[k][minc]] ; edge[nodey][nodex] = 1 ;
}
if( data[k][maxc]!='.'&&data[k][maxc]!=curn+'A' ) {
nodex = used[data[k][maxc]] ; edge[nodey][nodex] = 1 ;
}
}
}
void build_graph()
{
for( int i=0; i<row; i++ ) {
for( int j=0; j<col; j++ ) {
if( '.' == data[i][j] ) continue ;
find_edge( data[i][j] - 'A' ) ;
}
}
for( int i=1; i<cnt; i++ ) edge[i][i] = 0 ;
}
void process()
{
int curnode ;
for( int i=0; i<row; i++ ) {
for( int j=0; j<col; j++ ) {
if( data[i][j] != '.' ) {
curnode = data[i][j] - 'A' ;
node[curnode].minr = fmin( node[curnode].minr, i ) ;
node[curnode].minc = fmin( node[curnode].minc, j ) ;
node[curnode].maxr = fmax( node[curnode].maxr, i ) ;
node[curnode].maxc = fmax( node[curnode].maxc, j ) ;
}
}
}//尋找每個字母的矩形框
build_graph() ; //建圖
find_degree() ;//計算入度
ct_out = 0 ;
DFS_Topsort( 0, cnt-1 ) ;//拓撲排序
}
int cmp( const void *a, const void *b )
{
struct OUT *c = (struct OUT *)a ;
struct OUT *d = (struct OUT *)b ;
return strcmp( c->str, d->str ) ;
}
void output()
{
qsort( out, ct_out, sizeof(out[1]), cmp ) ;
for( int i=0; i<ct_out; i++ )
{
printf( "%s\n", out[i].str ) ;
}
}
int main()
{
freopen( "frameup.in", "r", stdin ) ;
freopen( "frameup.out","w",stdout ) ;
//freopen( "in.txt", "r", stdin ) ;
while( scanf( "%d %d", &row, &col ) != EOF )
{
input() ;
process() ;
output() ;
}
return 0 ;
}