首页 > 代码库 > POJ 1128 & ZOJ 1083 Frame Stacking (拓扑排序)
POJ 1128 & ZOJ 1083 Frame Stacking (拓扑排序)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=83
http://poj.org/problem?id=1128
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 DDDDAD.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 DDDDAD.A E...AAAA EEEEEE.. Sample Output EDABC Source Southern African 2001 |
题意：
给出若干张图片（矩形边框）叠在一起的效果图，保证边框为一个字符宽度，边长不短于3个字符，每条边都能看见一部分，每张图有且仅有一种字母且不重复，求出其从底到顶的叠放顺序，如果有多个解，按字典序输出每个解。题目保证有解。
分析：
首先要从凌乱的效果图中把每张图的信息抠出来，因为每条边保证可见，所以只要扫描四条边就行，得到了四条边的位置，就能确定某张图的位置。
图叠在一起只能看见每个位置顶部的图，也就是该位置有可能出现的图都在顶部那张图的下面，比如在（1,1）有A，B，C，D四张图，我们只能看见A，那么A在B，C，D的上面，即能确定A与B，C，D的相对位置。这样扫描全图，就能得到若干相对位置的信息。然后我们要得到一个合法的序列，即满足这些相对位置的信息，显然就是一个拓扑排序了。
题目要求的是所有的拓扑排序，且是字典序。由于点很少，那么就采用稍微暴力一点的方法。让我们先想一想如何求拓扑序。入度为0的点入栈/队，栈顶/队首元素出栈并进入拓扑序，然后删除其出边，如果有点的入度变成0,就把该点入栈/队，如此循环即可。我们仔细体会一下其中的过程：如果两个元素同时在栈/队中，那么他们之间的相对位置是无所谓的，这样就是多解的情况。如果要字典序最小的那组解，我们每次出栈/队的元素就是栈/队中最小的元素，这时候我们当然可以用优先队列来处理，由于这里点很少，索性就用一个数组标记哪些点可选（在栈/队中），然后遍历选择。多解的情况就有点像全排列了，想一想全排列该如何解，当然是回溯啦，这里我们用类似的方式进行深度优先搜索，就能按字典序得出所有的拓扑序了。
/*
*
* Author : fcbruce
*
* Date : 2014-08-10 09:39:26
*
*/
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10
#define maxm
#define maxn
using namespace std;
int h,w,n;
int L[30],R[30],U[30],D[30];
char MAP[33][33];
int fir[33][33];
int rec[33][33][30];
bool G[33][33];
int deg[33];
int topo[33];
bool pending[33];
void add_edge(int x,int y,int v)
{
for (int i=0;i<fir[x][y];i++)
if (rec[x][y][i]!=v && !G[rec[x][y][i]][v])
{
G[rec[x][y][i]][v]=true;
deg[v]++;
}
}
void init()
{
memset(L,-1,sizeof L);
memset(R,-1,sizeof R);
memset(U,-1,sizeof U);
memset(D,-1,sizeof D);
for (int i=0;i<h;i++)
{
for (int j=0;j<w;j++)
{
if (isalpha(MAP[i][j]) && U[MAP[i][j]-'A']==-1)
U[MAP[i][j]-'A']=i;
}
}
for (int i=h-1;i>=0;i--)
{
for (int j=0;j<w;j++)
{
if (isalpha(MAP[i][j]) && D[MAP[i][j]-'A']==-1)
D[MAP[i][j]-'A']=i;
}
}
for (int i=0;i<w;i++)
{
for (int j=0;j<h;j++)
{
if (isalpha(MAP[j][i]) && L[MAP[j][i]-'A']==-1)
L[MAP[j][i]-'A']=i;
}
}
for (int i=w-1;i>=0;i--)
{
for (int j=0;j<h;j++)
{
if (isalpha(MAP[j][i]) && R[MAP[j][i]-'A']==-1)
R[MAP[j][i]-'A']=i;
}
}
}
void build()
{
memset(fir,0,sizeof fir);
for (int i=0;;i++)
{
n=i;
if (L[i]==-1) break;
for (int j=L[i];j<=R[i];j++)
{
rec[U[i]][j][fir[U[i]][j]++]=i;
rec[D[i]][j][fir[D[i]][j]++]=i;
}
for (int j=U[i]+1;j<D[i];j++)
{
rec[j][L[i]][fir[j][L[i]]++]=i;
rec[j][R[i]][fir[j][R[i]]++]=i;
}
}
memset(G,0,sizeof G);
memset(deg,0,sizeof deg);
for (int i=0;i<h;i++)
{
for (int j=0;j<w;j++)
{
add_edge(i,j,MAP[i][j]-'A');
}
}
}
int st[33];
void write()
{
for (int i=0;i<n;i++)
putchar( st[i]+'A');
putchar ( '\n');
}
void toposort(int x,int top)
{
st[++top]=x;
if (top==n-1)
{
write();
return ;
}
for (int i=0;i<n;i++)
{
if (G[x][i])
{
deg[i]--;
if (deg[i]==0) pending[i]=true;
}
}
for (int i=0;i<n;i++)
{
if (pending[i])
{
pending[i]=false;
toposort(i,top);
pending[i]=true;
}
}
for (int i=0;i<n;i++)
{
if (G[x][i])
{
deg[i]++;
if (deg[i]!=0) pending[i]=false;
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("/home/fcbruce/文档/code/t","r",stdin);
#endif // ONLINE_JUDGE
while (~scanf ( "%d%d",&h,&w))
{
for (int i=0;i<h;i++)
{
scanf( "%s",MAP[i]);
}
init();
build();
memset(pending,0,sizeof pending);
for (int i=0;i<n;i++)
{
if (deg[i]==0)
{
pending[i]=true;
}
}
for (int i=0;i<n;i++)
{
if (pending[i])
{
pending[i]=false;
toposort(i,-1);
pending[i]=true;
}
}
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。