Frame Stacking
题目链接:http://poj.org/problem?id=1128
题目大意:
........ ........ ........ ........ .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
在9 * 8 的网格上,有上述5张图片。现在将他们摆放到同一个网格上。
如下图所示:
.CCC.... ECBCBB.. DCBCDB.. DCCC.B.. D.B.ABAA D.BBBB.A DDDDAD.A E...AAAA EEEEEE..
后摆放的图片会覆盖前面图片的字母。所以这张图片的摆放顺序可以为(EDABC)
现在给你一副已经摆好的图片,问你这幅图片是有哪些字母,按照怎样的顺序排出来的。按照字典序输出所有顺序。
解题思路:
题目主要是要建图,首先可以在图上找出每个字母的左上角和右下角坐标,然后每次对其中一个字母搜索,如果在该字母的位置上是其他字母,代表有有一条有向边。
建完图之后,就是输出拓扑排序的所有序列了。(由于图比较小,这里直接用DFS做了)
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <ctype.h> #include <vector> #include <algorithm> #define mem(a, b) memset(a, b, sizeof(a)) using namespace std; int h, w, g[35][35], has[30]; char mp[35][35]; struct node { int s, x, z, y; void inital() { s = z = 100; x = y = -1; } }e[35]; void init() { mem(g, 0); mem(has, 0); for (int i = 0; i < 26; i++) e[i].inital(); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin>>mp[i][j]; if (isalpha(mp[i][j])) { int u = mp[i][j] - 'A'; if (!has[u]) has[u] = 1; e[u].s = min(e[u].s, i); e[u].z = min(e[u].z, j); e[u].x = max(e[u].x, i); e[u].y = max(e[u].y, j); } } } for (int u = 0; u < 26; u++) if (has[u]) { for (int i = e[u].s; i <= e[u].x; i++) { int v1 = mp[i][e[u].z] - 'A', v2 = mp[i][e[u].y] - 'A'; if (v1 != u) g[u][v1] = 1; if (v2 != u) g[u][v2] = 1; } for (int j = e[u].z + 1; j < e[u].y; j++) { int v1 = mp[e[u].s][j] - 'A', v2 = mp[e[u].x][j] - 'A'; if (v1 != u) g[u][v1] = 1; if (v2 != u) g[u][v2] = 1; } } } int out[30], n, vis[30]; vector<int> v; void dfs(int x, int t) { if (t == n) { for (int i = 0; i < n; i++) printf("%c", out[i] + 'A'); puts(""); } for (int i = 0; i < n; i++) if (!vis[v[i]]) { int ok = 1; for (int j = 0; j < t; j++) if (g[v[i]][out[j]]) ok = 0; if (ok) { out[t] = v[i]; vis[v[i]] = 1; dfs(v[i], t + 1); vis[v[i]] = 0; } } } void gao() { v.clear(); for (int i = 0; i < 26; i++) if (has[i]) v.push_back(i); n = v.size(); mem(vis, 0); for (int i = 0; i < n; i++) { out[0] = v[i]; vis[v[i]] = 1; dfs(v[i], 1); vis[v[i]] = 0; } } int main () { while(scanf("%d%d", &h, &w) != EOF) { init(); gao(); } return 0; }