Southern African 2001 框架折叠 (拓扑序列的应用)

本文链接: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 有一条有向边，根据实际情况建立起来的图就是一个有向无环图，所以这个图上所有的拓扑序列就是答案。

代码:

  1 #include <stdio.h>  
  2 #include <string.h>  
  3 #include <iostream>  
  4 #include <queue>
  5 #include <stack>
  6 #include <algorithm>
  7 using namespace std;  
  8 
  9 const int MAXN = 26; //最多26个字母
 10 char Gra[MAXN][MAXN];//存储初始图
 11 int head[MAXN + 7];//用链式前向星存建立起来的图中
 12 int flag[MAXN + 7][MAXN + 7];//flag[i][j]用于判断i 和 j 之间是否有边，用于忽略掉重复边
 13 int h, w;//高h ， 宽 w
 14 int N; //图中一共有 N 个点
 15 int e;  //图中一共有 e 条边
 16 
 17 struct Map{ //把初始图先转为u v 之间存在的边，再转为链式前向星
 18     int u;
 19     int v;
 20 }map[MAXN * MAXN + 7]; 
 21 
 22 typedef struct EdgeNode{//链式前向星
 23     int to;
 24     int next;
 25 }edgeNode;
 26 edgeNode Edges[MAXN * MAXN + 7];
 27 
 28 typedef struct Point{//坐标
 29     int x;
 30     int y;
 31 }point;
 32 
 33 typedef struct Photo{//照片的位置
 34     point leftUp;//左上角
 35     point rightDown;//右下角
 36 }photos;
 37 photos pht[MAXN + 7];
 38 
 39 int getN()//由初始图获得节点的个数
 40 {
 41     int has[27] ={0};
 42     for(int i = 1; i <= h; i++)
 43         for(int j = 1; j <= w; j++)
 44             if(Gra[i][j] != '.')
 45                 has[ Gra[i][j] - 'A' ]++;    
 46     int n = 0;
 47     for(int i = 0; i <= 26; i++)
 48         if(has[i] != 0)
 49             n++;
 50     return n;
 51 }
 52 
 53 void getXY()//由初始图获得每个照片的两个对角坐标
 54 {
 55     for(int i = 1; i <= h; i++)
 56     {
 57         for(int j = 1; j <= w; j++)
 58         {
 59             for(int k = 1; k <= N; k++)
 60             {
 61                 if(Gra[i][j] != '.' && Gra[i][j] == k + 'A' - 1)
 62                 {
 63                     //cout << "*" << i << " " << j <<"*"<<endl;
 64                     pht[k].leftUp.x = min( pht[k].leftUp.x, i);
 65                     pht[k].leftUp.y = min( pht[k].leftUp.y, j);
 66                     pht[k].rightDown.x = max( pht[k].rightDown.x, i);
 67                     pht[k].rightDown.y = max( pht[k].rightDown.y, j);
 68                 }
 69             }
 70         }
 71     }
 72 }
 73 
 74 void initPht()//初始化对角坐标
 75 {
 76     for(int i = 0; i <= N; i++)
 77     {
 78         pht[i].leftUp.x = h + 1;
 79         pht[i].leftUp.y = w + 1;
 80         pht[i].rightDown.x = -1;
 81         pht[i].rightDown.y = -1;
 82     }
 83 }
 84 
 85 void buidEdge(photos pht, int m)//由初始图建立起来的一个基本图
 86 {
 87     int go;
 88     go = pht.leftUp.y;
 89     //cout << pht.leftUp.x << " " << pht.leftUp.y<<"     " << pht.rightDown.x <<" "<< pht.rightDown.y<<endl;
 90     while( go <= pht.rightDown.y)//横向遍历
 91     {
 92         //如果不是'.'，且不是本身，且之前尚未有边那么就建立起此边
 93         if( Gra[pht.leftUp.x][go] != '.' && Gra[pht.leftUp.x][go] != m + 'A' - 1 && flag[Gra[pht.leftUp.x][go] - 'A' + 1][m] != 1)
 94         {
 95             //cout << pht.leftUp.x << " ^ " << go << endl;
 96             ++e;
 97             flag[Gra[pht.leftUp.x][go] - 'A' + 1][m] = 1;
 98             map[e].v = Gra[pht.leftUp.x][go] - 'A' + 1;
 99             map[e].u = m;
100         }
101         if( Gra[pht.rightDown.x][go] != '.' && Gra[pht.rightDown.x][go] != m + 'A' - 1 && flag[Gra[ pht.rightDown.x][go] - 'A' + 1][m] != 1)
102         {
103             ++e;
104             flag[Gra[ pht.rightDown.x][go] - 'A' + 1][m] = 1;
105             map[e].v = Gra[pht.rightDown.x][go] - 'A' + 1;
106             map[e].u = m;
107         }
108         go++;
109     }
110     go = pht.leftUp.x;
111     while( go <= pht.rightDown.x)//纵向遍历
112     {
113         if( Gra[go][pht.rightDown.y] != '.' && Gra[go][pht.rightDown.y] != m + 'A' - 1 && flag[Gra[go][pht.rightDown.y] - 'A' + 1][m] != 1)
114         {
115             ++e;
116             flag[Gra[go][pht.rightDown.y] - 'A' + 1][m] = 1;
117             map[e].v = Gra[go][pht.rightDown.y] - 'A' + 1;
118             map[e].u = m;
119         }
120         if( Gra[go][pht.leftUp.y] != '.' && Gra[go][pht.leftUp.y] != m + 'A' - 1 && flag[Gra[go][pht.leftUp.y] - 'A' + 1][m] != 1)
121         {
122             ++e;
123             flag[Gra[go][pht.leftUp.y] - 'A' + 1][m] = 1;
124             map[e].v = Gra[go][pht.leftUp.y] - 'A' + 1;
125             map[e].u = m;
126         }
127         go++;
128     }
129 }
130 
131 int vis[MAXN + 7];
132 int indegree[MAXN + 7];
133 
134 void getIdg(int vis[])//获得每个点的入度
135 {
136     memset(indegree, 0, sizeof(indegree));
137     for(int i = 1;i <= N; i++)
138     {
139         if(!vis[i])
140         {
141             for(int j = head[i]; j != -1; j = Edges[j].next)
142             {
143                 indegree[Edges[j].to ] ++;
144             }
145         }
146     }
147 }
148 
149 int allVis()//每个点都被删了
150 {
151     for(int i = 1; i <= N; i++)
152         if(!vis[i])return 0;
153     return 1;
154 }
155 
156 void DFS(int head[], int vis[], queue<int> Qu)
157 {
158     queue<int> q;
159     getIdg(vis);
160     for(int i = 1; i <= N; i++) //每次把入度为 0 的点入到队列中
161     if(!vis[i] && !indegree[i]) q.push(i);
162     while(!q.empty())
163     {
164         int v = q.front();
165         q.pop();
166         queue<int> cpyQu(Qu);//复制Qu的副本并把 点 v 加入到Qu的副本中
167         cpyQu.push(v);
168         vis[v] = 1;        //删除已被访问到的点
169         int t = head[v];    
170         head[v] = 1;    //删除从这个点出发的全部有向边
171         if(allVis())    //如果图为空
172         {
173             while(!cpyQu.empty())
174             {
175                 cout <<(char) (cpyQu.front() + 'A' - 1) ;
176                 cpyQu.pop();
177             }
178             cout << endl;
179         }
180         else//继续递归剩下的图，
181             DFS(head, vis, cpyQu);
182         vis[v] = 0;//恢复现场
183         head[v] = t;
184     }
185 }
186 
187 int main() 
188 {
189     freopen("in.txt", "r", stdin);
190     //freopen("out.txt", "w", stdout);
191     while(~scanf("%d%d", &h, &w) && (h || w))
192     {
193         memset(Gra, 0, sizeof(Gra));
194         for(int i = 1; i <= h; i++)
195             scanf("%s",Gra[i] + 1);
196         N = getN();//获得N
197         initPht();//初始化图片对角的位置
198         getXY();//获得图片对角的位置
199         e = 0;
200         memset(flag, 0, sizeof(flag));
201         for(int i = 1; i <= N; i++)//建立基本图
202             buidEdge(pht[i], i);
203         memset(head, -1, sizeof(head));
204         memset(&Edges, 0, sizeof(EdgeNode));
205         memset(&pht, 0, sizeof(Photo));
206         for(int i = 1; i <= e; i++)//根据基本图建立链式前向星的存图结构
207         {
208             Edges[i].to = map[i].v;
209             Edges[i].next = head[map[i].u];
210             head[map[i].u] = i; 
211         }
212         memset(vis, 0, sizeof(vis));
213         queue<int> qu;
214         DFS(head, vis, qu);//head 用于删除图的边,vis删除边,qu是每次的拓扑序列
215     }
216     return 0;
217 }

提供一组测试数据：

/*
AAA*EEEE
ACCCECCE
ACA*E*CE
*C*DEEEE
*C*DD*C*
*C**BBCB
FFF*B*CB
FCFCCCCB
FFF*BBBB