本文链接:http://www.cnblogs.com/Ash-ly/p/5398377.html
题目：
考虑五个图片堆叠在一起，比如下面的9 * 8 的矩阵表示的是这些图片的边缘框。
现在上面的图片顺序为图片1放在最底下，5放在最顶上。如果任何图片的边框覆盖了其他图片的边框，被覆盖的部分不会被显示出来。
下面是一个栗子:
那么从低向上图片的堆叠顺序为 EDABC，现在的问题是给出一个堆叠后的表示，要确定从低向上的图片的堆叠顺序。
下面是判定规则：
1、图片一定是由一个字母表示并且每条边至少三个字符
2、题目保证至少会给出每条边的一个字母，一个角的一个字符代表两条边
3、图片边框用大写字母表示，并且不会有俩张图片的边框使用同一个大写字母
输入：
高度h 、宽度w、接下来是一个h * w 的矩阵，输入数据可能包括多组，中间没有空行
输出：
输出自底向上形成输入状况的图片边框所对应的字母。如果有多组排列方式，将所有的序列按照字母序排列输出。每个可行的序列战一行，对于每个输入确保至少有一个合法的序列满足题意。两组数据之间没有空格。
解题思路：
首先由于题目中的第二个条件，所以就可以把每个图片的四个角的坐标找到，但是其实只要俩个对角的坐标就可以确定这个图片的位置了，所以只需要找到每个图片的俩个对角的坐标就行了，然后就需要对图再进行一次遍历，如果在应该出现A的地方出现了B那么说明B应该在A的上面，即B覆盖了A。然后就可以把图片边框之间的上下层次关系确定下来，之后就可以利用到拓扑排序了，如果A在B下面，那么我们就认为 Va –> Vb 有一条有向边，根据实际情况建立起来的图就是一个有向无环图，所以这个图上所有的拓扑序列就是答案。
代码:
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std; const int MAXN = ; //最多26个字母
char Gra[MAXN][MAXN];//存储初始图
int head[MAXN + ];//用链式前向星存建立起来的图中
int flag[MAXN + ][MAXN + ];//flag[i][j]用于判断i 和 j 之间是否有边，用于忽略掉重复边
int h, w;//高h ， 宽 w
int N; //图中一共有 N 个点
int e; //图中一共有 e 条边 struct Map{ //把初始图先转为u v 之间存在的边，再转为链式前向星
int u;
int v;
}map[MAXN * MAXN + ]; typedef struct EdgeNode{//链式前向星
int to;
int next;
}edgeNode;
edgeNode Edges[MAXN * MAXN + ]; typedef struct Point{//坐标
int x;
int y;
}point; typedef struct Photo{//照片的位置
point leftUp;//左上角
point rightDown;//右下角
}photos;
photos pht[MAXN + ]; int getN()//由初始图获得节点的个数
{
int has[] ={};
for(int i = ; i <= h; i++)
for(int j = ; j <= w; j++)
if(Gra[i][j] != '.')
has[ Gra[i][j] - 'A' ]++;
int n = ;
for(int i = ; i <= ; i++)
if(has[i] != )
n++;
return n;
} void getXY()//由初始图获得每个照片的两个对角坐标
{
for(int i = ; i <= h; i++)
{
for(int j = ; j <= w; j++)
{
for(int k = ; k <= N; k++)
{
if(Gra[i][j] != '.' && Gra[i][j] == k + 'A' - )
{
//cout << "*" << i << " " << j <<"*"<<endl;
pht[k].leftUp.x = min( pht[k].leftUp.x, i);
pht[k].leftUp.y = min( pht[k].leftUp.y, j);
pht[k].rightDown.x = max( pht[k].rightDown.x, i);
pht[k].rightDown.y = max( pht[k].rightDown.y, j);
}
}
}
}
} void initPht()//初始化对角坐标
{
for(int i = ; i <= N; i++)
{
pht[i].leftUp.x = h + ;
pht[i].leftUp.y = w + ;
pht[i].rightDown.x = -;
pht[i].rightDown.y = -;
}
} void buidEdge(photos pht, int m)//由初始图建立起来的一个基本图
{
int go;
go = pht.leftUp.y;
//cout << pht.leftUp.x << " " << pht.leftUp.y<<" " << pht.rightDown.x <<" "<< pht.rightDown.y<<endl;
while( go <= pht.rightDown.y)//横向遍历
{
//如果不是'.'，且不是本身，且之前尚未有边那么就建立起此边
if( Gra[pht.leftUp.x][go] != '.' && Gra[pht.leftUp.x][go] != m + 'A' - && flag[Gra[pht.leftUp.x][go] - 'A' + ][m] != )
{
//cout << pht.leftUp.x << " ^ " << go << endl;
++e;
flag[Gra[pht.leftUp.x][go] - 'A' + ][m] = ;
map[e].v = Gra[pht.leftUp.x][go] - 'A' + ;
map[e].u = m;
}
if( Gra[pht.rightDown.x][go] != '.' && Gra[pht.rightDown.x][go] != m + 'A' - && flag[Gra[ pht.rightDown.x][go] - 'A' + ][m] != )
{
++e;
flag[Gra[ pht.rightDown.x][go] - 'A' + ][m] = ;
map[e].v = Gra[pht.rightDown.x][go] - 'A' + ;
map[e].u = m;
}
go++;
}
go = pht.leftUp.x;
while( go <= pht.rightDown.x)//纵向遍历
{
if( Gra[go][pht.rightDown.y] != '.' && Gra[go][pht.rightDown.y] != m + 'A' - && flag[Gra[go][pht.rightDown.y] - 'A' + ][m] != )
{
++e;
flag[Gra[go][pht.rightDown.y] - 'A' + ][m] = ;
map[e].v = Gra[go][pht.rightDown.y] - 'A' + ;
map[e].u = m;
}
if( Gra[go][pht.leftUp.y] != '.' && Gra[go][pht.leftUp.y] != m + 'A' - && flag[Gra[go][pht.leftUp.y] - 'A' + ][m] != )
{
++e;
flag[Gra[go][pht.leftUp.y] - 'A' + ][m] = ;
map[e].v = Gra[go][pht.leftUp.y] - 'A' + ;
map[e].u = m;
}
go++;
}
} int vis[MAXN + ];
int indegree[MAXN + ]; void getIdg(int vis[])//获得每个点的入度
{
memset(indegree, , sizeof(indegree));
for(int i = ;i <= N; i++)
{
if(!vis[i])
{
for(int j = head[i]; j != -; j = Edges[j].next)
{
indegree[Edges[j].to ] ++;
}
}
}
} int allVis()//每个点都被删了
{
for(int i = ; i <= N; i++)
if(!vis[i])return ;
return ;
} void DFS(int head[], int vis[], queue<int> Qu)
{
queue<int> q;
getIdg(vis);
for(int i = ; i <= N; i++) //每次把入度为 0 的点入到队列中
if(!vis[i] && !indegree[i]) q.push(i);
while(!q.empty())
{
int v = q.front();
q.pop();
queue<int> cpyQu(Qu);//复制Qu的副本并把 点 v 加入到Qu的副本中
cpyQu.push(v);
vis[v] = ; //删除已被访问到的点
int t = head[v];
head[v] = ; //删除从这个点出发的全部有向边
if(allVis()) //如果图为空
{
while(!cpyQu.empty())
{
cout <<(char) (cpyQu.front() + 'A' - ) ;
cpyQu.pop();
}
cout << endl;
}
else//继续递归剩下的图，
DFS(head, vis, cpyQu);
vis[v] = ;//恢复现场
head[v] = t;
}
} int main()
{
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(~scanf("%d%d", &h, &w) && (h || w))
{
memset(Gra, , sizeof(Gra));
for(int i = ; i <= h; i++)
scanf("%s",Gra[i] + );
N = getN();//获得N
initPht();//初始化图片对角的位置
getXY();//获得图片对角的位置
e = ;
memset(flag, , sizeof(flag));
for(int i = ; i <= N; i++)//建立基本图
buidEdge(pht[i], i);
memset(head, -, sizeof(head));
memset(&Edges, , sizeof(EdgeNode));
memset(&pht, , sizeof(Photo));
for(int i = ; i <= e; i++)//根据基本图建立链式前向星的存图结构
{
Edges[i].to = map[i].v;
Edges[i].next = head[map[i].u];
head[map[i].u] = i;
}
memset(vis, , sizeof(vis));
queue<int> qu;
DFS(head, vis, qu);//head 用于删除图的边,vis删除边,qu是每次的拓扑序列
}
return ;
}
提供一组测试数据：
/*
AAA*EEEE
ACCCECCE
ACA*E*CE
*C*DEEEE
*C*DD*C*
*C**BBCB
FFF*B*CB
FCFCCCCB
FFF*BBBB
*/
