This post is written in Chinese. Please consider using Google Translate

由题意可知，不存在一个矩形的一条边被完全覆盖，所以我们可以计算出矩形的坐标。 读入时记录矩形的每个点中最小x1，最小y1，最大x2，最大y2。可知左上角 (x1,y1) 右下角 (x2,y2) 右上角 (x2,y1) 左下角 (x1,y2)。

查找该矩形A边上，非该矩形的字母B，即覆盖矩形A被矩形B覆盖。建立一条有向边B->A，表示B是A的必要条件。然后进行拓扑排序，搜索求所有的拓扑序列，并排序输出。

注意，该题中的字母可能不连续，不要直接for(i='A';i<='Z';i++)。

USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: frameup
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3116 KB]
   Test 2: TEST OK [0.000 secs, 3112 KB]
   Test 3: TEST OK [0.011 secs, 3112 KB]
   Test 4: TEST OK [0.022 secs, 3112 KB]
   Test 5: TEST OK [0.011 secs, 3112 KB]
   Test 6: TEST OK [0.000 secs, 3116 KB]
   Test 7: TEST OK [0.011 secs, 3116 KB]
   Test 8: TEST OK [0.043 secs, 3116 KB]
   Test 9: TEST OK [0.162 secs, 3112 KB]

All tests OK.

Your program ('frameup') produced all correct answers!  This is your
submission #3 for this problem.  Congratulations!

/*
ID: cmykrgb1
PROG: frameup
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 'Z'+1
#define MAXA 10000
using namespace std;

ifstream fi("frameup.in");
ofstream fo("frameup.out");

typedef struct
{
    char m[26];
}Tans;

int N,M,len,acnt;
int map[30][30];
bool dis[MAX][MAX],usd[MAX],cu[MAX];
int x1[MAX],x2[MAX],y1[MAX],y2[MAX];
char L,start,use[MAX];
Tans ans[MAXA];

void init()
{
    int i,j,k;
    char c,p;
    memset(x1,1,sizeof(x1));
    memset(y1,1,sizeof(y1));
    fi >> N >> M;
    c=fi.get();
    for (i=0;i<N;i++)
    {
        for (j=0;j<M;j++)
        {
            map[i][j]=c=fi.get();
            cu[c]=true;
            if (c>L) L=c;
            if (i<x1[c]) x1[c]=i;
            if (j<y1[c]) y1[c]=j;
            if (i>x2[c]) x2[c]=i;
            if (j>y2[c]) y2[c]=j;
        }
        c=fi.get();
    }

    len=0;
    for (c='A';c<=L;c++)
    {
        if (!cu[c]) continue;
        len++;
        k=0;
        i=x1[c];
        for (j=y1[c];j<=y2[c];j++)
        {
            p=map[i][j];
            if (p!=c)
            {
                dis[p][c]=true;
                k++;
            }
        }
        i=x2[c];
        for (j=y1[c];j<=y2[c];j++)
        {
            p=map[i][j];
            if (p!=c)
            {
                dis[p][c]=true;
                k++;
            }
        }
        j=y1[c];
        for (i=x1[c]+1;i<=x2[c]-1;i++)
        {
            p=map[i][j];
            if (p!=c)
            {
                dis[p][c]=true;
                k++;
            }
        }
        j=y2[c];
        for (i=x1[c]+1;i<=x2[c]-1;i++)
        {
            p=map[i][j];
            if (p!=c)
            {
                dis[p][c]=true;
                k++;
            }
        }

        if (k==0)
            start=c;
    }
}

bool noprefix(char c)
{
    char p;
    for (p='A';p<=L;p++)
    {
        if (!cu[p]) continue;
        if (dis[p][c] && !usd[p])
            return false;
    }
    return true;
}

void dfs(char c,int k)
{
    if (k==len)
    {
        int i;
        acnt++;
        for (i=0;i<k;i++)
            ans[acnt].m[i]=use[k-i-1];
        return;
    }

    usd[c]=true;
    char p;
    for (p='A';p<=L;p++)
    {
        if (!cu[p]) continue;
        if (!usd[p] && noprefix(p))
        {
            use[k]=p;
            dfs(p,k+1);
        }
    }
    usd[c]=false;
}

int cmp(const void *a,const void *b)
{
    return strcmp( (*(Tans *)a).m , (*(Tans *)b).m ); 
}

void print()
{
    int i;
    qsort(ans+1,acnt,sizeof(ans[0]),cmp);
    for (i=1;i<=acnt;i++)
        fo << ans[i].m << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    for (start='A';start<=L;start++)
    {
        if (!cu[start] || !noprefix(start)) continue;
        use[0]=start;
        dfs(start,1);
    }
    print();
    return 0;
}