# POJ1128总结

## Frame Stacking

### Description

Consider the following 5 picture frames placed on an 9 x 8 array.

........ ........ ........ ........ .CCC....
EEEEEE.. ........ ........ ..BBBB.. .C.C....
E....E.. DDDDDD.. ........ ..B..B.. .C.C....
E....E.. D....D.. ........ ..B..B.. .CCC....
E....E.. D....D.. ....AAAA ..B..B.. ........
E....E.. D....D.. ....A..A ..BBBB.. ........
E....E.. DDDDDD.. ....A..A ........ ........
E....E.. ........ ....AAAA ........ ........
EEEEEE.. ........ ........ ........ ........
1        2        3        4        5   

Now place them on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another it hides that part of the frame below.

Viewing the stack of 5 frames we see the following.

.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
E...AAAA
EEEEEE..



In what order are the frames stacked from bottom to top? The answer is EDABC.

Your problem is to determine the order in which the frames are stacked from bottom to top given a picture of the stacked frames. Here are the rules:

1. The width of the frame is always exactly 1 character and the sides are never shorter than 3 characters.

2. It is possible to see at least one part of each of the four sides of a frame. A corner shows two sides.

3. The frames will be lettered with capital letters, and no two frames will be assigned the same letter.

### Input

Each input block contains the height, h (h<=30) on the first line and the width w (w<=30) on the second. A picture of the stacked frames is then given as h strings with w characters each.
Your input may contain multiple blocks of the format described above, without any blank lines in between. All blocks in the input must be processed sequentially.

### Output

Write the solution to the standard output. Give the letters of the frames in the order they were stacked from bottom to top. If there are multiple possibilities for an ordering, list all such possibilities in alphabetical order, each one on a separate line. There will always be at least one legal ordering for each input block. List the output for all blocks in the input sequentially, without any blank lines (not even between blocks).

### Sample Input

9
8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
E...AAAA
EEEEEE..

### Sample Output

EDABC

### 第一次通过的代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int h,w,num,ans_num;//h为高度，w为宽度，num为所用的字母个数，ans_num为答案个数
int flag[26]={0};//标记'A'+i号字母是否被用
struct alphbet
//这个是每一个字母的信息
{
char alph;//记录字母
int top,bot,left,right;//记录这个字母框的上下左右的坐标
}list[26];
//记录所有答案，为了排序
{
char alph[26];
}ans[40320];
char picture[31][31];//记录图片
//对答案排序
{
if (strcmp(a.alph,b.alph)<0) return 1;
else return 0;
}
//找框架的上界坐标
int seektop(char c)
{
for (int i=0;i<h;i++)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
//找框架的下界坐标
int seekbot(char c)
{
for (int i=h-1;i>=0;i--)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
//找框架的左界坐标
int seekleft(char c)
{
for (int i=0;i<w;i++)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
//找框架的右界坐标
int seekright(char c)
{
for (int i=w-1;i>=0;i--)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
//判断这个字母是否被其它字母挡住
int check(int c)
{
for (int i=list[c].left;i<=list[c].right;i++)
{
if (picture[list[c].top][i]!=list[c].alph&&picture[list[c].top][i]!='.') return 0;
if (picture[list[c].bot][i]!=list[c].alph&&picture[list[c].bot][i]!='.') return 0;
}
for (int i=list[c].top;i<=list[c].bot;i++)
{
if (picture[i][list[c].left]!=list[c].alph&&picture[i][list[c].left]!='.') return 0;
if (picture[i][list[c].right]!=list[c].alph&&picture[i][list[c].right]!='.') return 0;
}
return 1;
}
int dfs(int n,int t)
{
if (t==n+1)
//递归出口，将答案存储进结构体中
{
ans[ans_num].alph[n]='#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int h,w,num,ans_num;//h为高度，w为宽度，num为所用的字母个数，ans_num为答案个数
int flag[26]={0};//标记'A'+i号字母是否被用
struct alphbet
//这个是每一个字母的信息
{
char alph;//记录字母
int top,bot,left,right;//记录这个字母框的上下左右的坐标
}list[26];
//记录所有答案，为了排序
{
char alph[26];
}ans[40320];
char picture[31][31];//记录图片
//对答案排序
{
if (strcmp(a.alph,b.alph)<0) return 1;
else return 0;
}
//找框架的上界坐标
int seektop(char c)
{
for (int i=0;i<h;i++)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
//找框架的下界坐标
int seekbot(char c)
{
for (int i=h-1;i>=0;i--)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
//找框架的左界坐标
int seekleft(char c)
{
for (int i=0;i<w;i++)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
//找框架的右界坐标
int seekright(char c)
{
for (int i=w-1;i>=0;i--)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
//判断这个字母是否被其它字母挡住
int check(int c)
{
for (int i=list[c].left;i<=list[c].right;i++)
{
if (picture[list[c].top][i]!=list[c].alph&&picture[list[c].top][i]!='.') return 0;
if (picture[list[c].bot][i]!=list[c].alph&&picture[list[c].bot][i]!='.') return 0;
}
for (int i=list[c].top;i<=list[c].bot;i++)
{
if (picture[i][list[c].left]!=list[c].alph&&picture[i][list[c].left]!='.') return 0;
if (picture[i][list[c].right]!=list[c].alph&&picture[i][list[c].right]!='.') return 0;
}
return 1;
}
int dfs(int n,int t)
{
if (t==n+1)
//递归出口，将答案存储进结构体中
{
ans[ans_num].alph[n]='\0';
strcpy(ans[ans_num+1].alph,ans[ans_num].alph);
ans_num++;
return 1;
}
else
{
for (int i=0;i<n;i++)
{
if (flag[list[i].alph-'A'])
//如果该字母被使用
{
if (check(i))
//如果这个字母没被挡住
{
//将这个字母框架从图中拆了
for (int j=list[i].left;j<=list[i].right;j++)
{
picture[list[i].top][j]='.';
picture[list[i].bot][j]='.';
}
for (int j=list[i].top;j<=list[i].bot;j++)
{
picture[j][list[i].left]='.';
picture[j][list[i].right]='.';
}
//因为暂时被拆了，所以图上暂时没有这个字母
flag[list[i].alph-'A']=0;
//将这个字母存到答案序列中
ans[ans_num].alph[n-t]=list[i].alph;
//递归下一个
dfs(n,t+1);
//回溯，把这个框架装上去
flag[list[i].alph-'A']=1;
for (int j=list[i].left;j<=list[i].right;j++)
{
picture[list[i].top][j]=list[i].alph;
picture[list[i].bot][j]=list[i].alph;
}
for (int j=list[i].top;j<=list[i].bot;j++)
{
picture[j][list[i].left]=list[i].alph;
picture[j][list[i].right]=list[i].alph;
}
}
}
}
}
}
int main()
{
char c;
while (scanf("%d%d",&h,&w)==2)
{
num=0;
ans_num=0;
for (int i=0;i<26;i++)
{
flag[i]=0;
}
for (int i=0;i<h;i++)
{
c=getchar();
for (int j=0;j<w;j++)
{
scanf("%c",&picture[i][j]);
if (picture[i][j]!='.')	flag[picture[i][j]-'A']=1;
}
}
for (int i=0;i<26;i++)
{
if (flag[i])
//如果一个字母被使用，就将其加入到list中，并且寻找其框架的边界位置
{
list[num].alph=(char)('A'+i);
list[num].top=seektop((char)('A'+i));
list[num].bot=seekbot((char)('A'+i));
list[num].left=seekleft((char)('A'+i));
list[num].right=seekright((char)('A'+i));
num++;
}
}
dfs(num,1);
//排序
sort(ans,(ans+ans_num),cmp);
for (int i=0;i<ans_num;i++)
{
for (int j=0;j<num;j++)
printf("%c",ans[i].alph[j]);
printf ("\n");
}
}
return 0;
}';
strcpy(ans[ans_num+1].alph,ans[ans_num].alph);
ans_num++;
return 1;
}
else
{
for (int i=0;i<n;i++)
{
if (flag[list[i].alph-'A'])
//如果该字母被使用
{
if (check(i))
//如果这个字母没被挡住
{
//将这个字母框架从图中拆了
for (int j=list[i].left;j<=list[i].right;j++)
{
picture[list[i].top][j]='.';
picture[list[i].bot][j]='.';
}
for (int j=list[i].top;j<=list[i].bot;j++)
{
picture[j][list[i].left]='.';
picture[j][list[i].right]='.';
}
//因为暂时被拆了，所以图上暂时没有这个字母
flag[list[i].alph-'A']=0;
//将这个字母存到答案序列中
ans[ans_num].alph[n-t]=list[i].alph;
//递归下一个
dfs(n,t+1);
//回溯，把这个框架装上去
flag[list[i].alph-'A']=1;
for (int j=list[i].left;j<=list[i].right;j++)
{
picture[list[i].top][j]=list[i].alph;
picture[list[i].bot][j]=list[i].alph;
}
for (int j=list[i].top;j<=list[i].bot;j++)
{
picture[j][list[i].left]=list[i].alph;
picture[j][list[i].right]=list[i].alph;
}
}
}
}
}
}
int main()
{
char c;
while (scanf("%d%d",&h,&w)==2)
{
num=0;
ans_num=0;
for (int i=0;i<26;i++)
{
flag[i]=0;
}
for (int i=0;i<h;i++)
{
c=getchar();
for (int j=0;j<w;j++)
{
scanf("%c",&picture[i][j]);
if (picture[i][j]!='.')	flag[picture[i][j]-'A']=1;
}
}
for (int i=0;i<26;i++)
{
if (flag[i])
//如果一个字母被使用，就将其加入到list中，并且寻找其框架的边界位置
{
list[num].alph=(char)('A'+i);
list[num].top=seektop((char)('A'+i));
list[num].bot=seekbot((char)('A'+i));
list[num].left=seekleft((char)('A'+i));
list[num].right=seekright((char)('A'+i));
num++;
}
}
dfs(num,1);
//排序
sort(ans,(ans+ans_num),cmp);
for (int i=0;i<ans_num;i++)
{
for (int j=0;j<num;j++)
printf("%c",ans[i].alph[j]);
printf ("\n");
}
}
return 0;
}

### 第二次通过的代码 拓扑排序

(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int h,w,num,ans_num;
int flag[26]={0};
int have[26][26]={0};//have[i][j]记录j是否在i的上方，即j是否是i的先行节点
char picture[31][31];
char temp[26];//记录当前的答案
int map[26][26];//构造有向无环图
struct alphbet
{
char alph;
int top,bot,left,right;
int in;//记录入度
char fore[16];//记录先行节点
alphbet(){in=0;}
}list[26];
{
char alph[26];
}ans[40320];
{
if (strcmp(a.alph,b.alph)<0) return 1;
else return 0;
}
int seektop(char c)
{
for (int i=0;i<h;i++)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
int seekbot(char c)
{
for (int i=h-1;i>=0;i--)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
int seekleft(char c)
{
for (int i=0;i<w;i++)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
int seekright(char c)
{
for (int i=w-1;i>=0;i--)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
//构造有向无环图
void buildmap()
{
for (int i=0;i<num;i++)
{
if (flag[list[i].alph-'A'])
{
//寻找自己的框架上有哪些其它的字母，这些字母就是这个框架的先行字母
for (int j=list[i].top;j<=list[i].bot;j++)
{
if (picture[j][list[i].left]!='.'&&picture[j][list[i].left]!=list[i].alph)
{have[list[i].alph-'A'][picture[j][list[i].left]-'A']=1;}
if (picture[j][list[i].right]!='.'&&picture[j][list[i].right]!=list[i].alph)
{have[list[i].alph-'A'][picture[j][list[i].right]-'A']=1;}
}
for (int j=list[i].left;j<=list[i].right;j++)
{
if (picture[list[i].top][j]!='.'&&picture[list[i].top][j]!=list[i].alph)
{have[list[i].alph-'A'][picture[list[i].top][j]-'A']=1;}
if (picture[list[i].bot][j]!='.'&&picture[list[i].bot][j]!=list[i].alph)
{have[list[i].alph-'A'][picture[list[i].bot][j]-'A']=1;}
}
for (int j=0;j<26;j++)
{
if (have[list[i].alph-'A'][j])
{
list[i].fore[list[i].in++]=(char)(j+'A');
}
}
}
}
}
void topoSort(int u,int t)
{
temp[t]=list[u].alph;
if (t==num)
//递归出口将答案赋值给结构体
{
for (int i=1;i<=num;i++) ans[ans_num].alph[i-1]=temp[num-i+1];
ans[ans_num].alph[num]='#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int h,w,num,ans_num;
int flag[26]={0};
int have[26][26]={0};//have[i][j]记录j是否在i的上方，即j是否是i的先行节点
char picture[31][31];
char temp[26];//记录当前的答案
int map[26][26];//构造有向无环图
struct alphbet
{
char alph;
int top,bot,left,right;
int in;//记录入度
char fore[16];//记录先行节点
alphbet(){in=0;}
}list[26];
{
char alph[26];
}ans[40320];
{
if (strcmp(a.alph,b.alph)<0) return 1;
else return 0;
}
int seektop(char c)
{
for (int i=0;i<h;i++)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
int seekbot(char c)
{
for (int i=h-1;i>=0;i--)
{
for (int j=0;j<w;j++)
{
if (picture[i][j]==c) return i;
}
}
}
int seekleft(char c)
{
for (int i=0;i<w;i++)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
int seekright(char c)
{
for (int i=w-1;i>=0;i--)
{
for (int j=0;j<h;j++)
{
if (picture[j][i]==c) return i;
}
}
}
//构造有向无环图
void buildmap()
{
for (int i=0;i<num;i++)
{
if (flag[list[i].alph-'A'])
{
//寻找自己的框架上有哪些其它的字母，这些字母就是这个框架的先行字母
for (int j=list[i].top;j<=list[i].bot;j++)
{
if (picture[j][list[i].left]!='.'&&picture[j][list[i].left]!=list[i].alph)
{have[list[i].alph-'A'][picture[j][list[i].left]-'A']=1;}
if (picture[j][list[i].right]!='.'&&picture[j][list[i].right]!=list[i].alph)
{have[list[i].alph-'A'][picture[j][list[i].right]-'A']=1;}
}
for (int j=list[i].left;j<=list[i].right;j++)
{
if (picture[list[i].top][j]!='.'&&picture[list[i].top][j]!=list[i].alph)
{have[list[i].alph-'A'][picture[list[i].top][j]-'A']=1;}
if (picture[list[i].bot][j]!='.'&&picture[list[i].bot][j]!=list[i].alph)
{have[list[i].alph-'A'][picture[list[i].bot][j]-'A']=1;}
}
for (int j=0;j<26;j++)
{
if (have[list[i].alph-'A'][j])
{
list[i].fore[list[i].in++]=(char)(j+'A');
}
}
}
}
}
void topoSort(int u,int t)
{
temp[t]=list[u].alph;
if (t==num)
//递归出口将答案赋值给结构体
{
for (int i=1;i<=num;i++) ans[ans_num].alph[i-1]=temp[num-i+1];
ans[ans_num].alph[num]='\0';
ans_num++;
return;
}
else
{
//拆掉这个框架
//这个框架下的所有框架入度减一
for (int i=0;i<26;i++)
{
if (have[i][u])	list[i].in--;
}
//将其入度标为-1
list[u].in=-1;
//寻找下一个入度为0的字母
for (int i=0;i<num;i++)
{
if (list[i].in==0)	topoSort(i,t+1);
}
//回溯
for (int i=0;i<26;i++)
{
if (have[i][u])	list[i].in++;
}
list[u].in=0;
}
}
int main()
{
char c;
while (scanf("%d%d",&h,&w)==2)
{
num=0;
ans_num=0;
memset(flag,0,sizeof(flag));
memset(map,0,sizeof(map));
memset(have,0,sizeof(have));
for (int i=0;i<h;i++)
{
c=getchar();
for (int j=0;j<w;j++)
{
scanf("%c",&picture[i][j]);
if (picture[i][j]!='.')	flag[picture[i][j]-'A']=1;
}
}
for (int i=0;i<26;i++)
{
if (flag[i])
{
list[num].alph=(char)('A'+i);
list[num].top=seektop((char)('A'+i));
list[num].bot=seekbot((char)('A'+i));
list[num].left=seekleft((char)('A'+i));
list[num].right=seekright((char)('A'+i));
num++;
}
}
buildmap();
for (int i=0;i<num;i++)
{
if (list[i].in==0)	topoSort(i,1);
}
sort(ans,(ans+ans_num),cmp);
for (int i=0;i<ans_num;i++)
{
for (int j=0;j<num;j++)
printf("%c",ans[i].alph[j]);
printf ("\n");
}
for (int i=0;i<num;i++)
{
for (int j=0;j<list[i].in;j++);
list[i].in=0;
}
}
return 0;
}';
ans_num++;
return;
}
else
{
//拆掉这个框架
//这个框架下的所有框架入度减一
for (int i=0;i<26;i++)
{
if (have[i][u])	list[i].in--;
}
//将其入度标为-1
list[u].in=-1;
//寻找下一个入度为0的字母
for (int i=0;i<num;i++)
{
if (list[i].in==0)	topoSort(i,t+1);
}
//回溯
for (int i=0;i<26;i++)
{
if (have[i][u])	list[i].in++;
}
list[u].in=0;
}
}
int main()
{
char c;
while (scanf("%d%d",&h,&w)==2)
{
num=0;
ans_num=0;
memset(flag,0,sizeof(flag));
memset(map,0,sizeof(map));
memset(have,0,sizeof(have));
for (int i=0;i<h;i++)
{
c=getchar();
for (int j=0;j<w;j++)
{
scanf("%c",&picture[i][j]);
if (picture[i][j]!='.')	flag[picture[i][j]-'A']=1;
}
}
for (int i=0;i<26;i++)
{
if (flag[i])
{
list[num].alph=(char)('A'+i);
list[num].top=seektop((char)('A'+i));
list[num].bot=seekbot((char)('A'+i));
list[num].left=seekleft((char)('A'+i));
list[num].right=seekright((char)('A'+i));
num++;
}
}
buildmap();

for (int i=0;i<num;i++)
{
if (list[i].in==0)	topoSort(i,1);
}
sort(ans,(ans+ans_num),cmp);
for (int i=0;i<ans_num;i++)
{
for (int j=0;j<num;j++)
printf("%c",ans[i].alph[j]);
printf ("\n");
}
for (int i=0;i<num;i++)
{
for (int j=0;j<list[i].in;j++);

list[i].in=0;
}
}
return 0;
}

### 反思

struct answer
//记录所有答案，为了排序
{
char alph[26];
}ans[40320];
char picture[31][31];//记录图片
//对答案排序
}