/*
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 ;
}