問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1128思路:
想法是有：先找出沒有被任何其他frame覆蓋的frame，然后將該frame進行標(biāo)記，使之匹配任何字母，然后重復(fù)以上過程
不過，程序不知道該如何寫
參考discuss以及其他人思路，發(fā)現(xiàn)可以用拓撲排序來做（拓撲排序，參考算法導(dǎo)論)
如何根據(jù)輸入來建立鄰接矩陣比較有意思，另外根據(jù)各個頂點的入度DFS實現(xiàn)拓撲排序
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 31
5 #define MAX_NUM 27
6 char map[MAX_LEN][MAX_LEN];
7 int n, m;
8 int adj[MAX_NUM][MAX_NUM], num, in[MAX_NUM], visited[MAX_NUM];
9 int x1, y1, x2, y2;
10
11 void
12 search(char ch)
13 {
14 int i, j;
15 x1 = y1 = MAX_LEN;
16 x2 = y2 = -1;
17 for(i=0; i<n; i++)
18 for(j=0; j<m; j++)
19 if(map[i][j] == ch) {
20 if(i<x1) x1 = i;
21 if(i>x2) x2 = i;
22 if(j<y1) y1 = j;
23 if(j>y2) y2 = j;
24 }
25 }
26
27 void
28 build_graph()
29 {
30 int i, j, k;
31 char ch;
32 num = 0;
33 memset(adj, 0, sizeof(adj));
34 memset(in, -1, sizeof(in));
35 for(i=0; i<n; i++) {
36 for(j=0; j<m; j++) {
37 if(map[i][j]=='.' || in[map[i][j]-'A']>-1)
38 continue;
39 in[map[i][j]-'A'] = 0;
40 ++num;
41 search(map[i][j]);
42 for(k=x1; k<=x2; k++) {
43 ch = map[k][y1];
44 if(ch != map[i][j])
45 adj[map[i][j]-'A'][ch-'A'] = 1;
46 }
47 for(k=x1; k<=x2; k++) {
48 ch = map[k][y2];
49 if(ch != map[i][j])
50 adj[map[i][j]-'A'][ch-'A'] = 1;
51 }
52 for(k=y1; k<=y2; k++) {
53 ch = map[x1][k];
54 if(ch != map[i][j])
55 adj[map[i][j]-'A'][ch-'A'] = 1;
56 }
57 for(k=y1; k<=y2; k++) {
58 ch = map[x2][k];
59 if(ch != map[i][j])
60 adj[map[i][j]-'A'][ch-'A'] = 1;
61 }
62 }
63 }
64 for(i=0; i<MAX_NUM; i++)
65 for(j=0; j<MAX_NUM; j++)
66 if(adj[i][j])
67 ++in[j]; /* in-degree */
68 }
69
70 void
71 topological_sort(char *str, int level)
72 {
73 int i, j;
74 if(level == num) {
75 printf("%s\n", str);
76 return;
77 }
78 for(i=0; i<MAX_NUM; i++) {
79 if(in[i]==0 && !visited[i]) {
80 str[level] = 'A'+i;
81 visited[i] = 1;
82 for(j=0; j<MAX_NUM; j++)
83 if(adj[i][j])
84 --in[j];
85 topological_sort(str, level+1);
86 visited[i] = 0;
87 for(j=0; j<MAX_NUM; j++)
88 if(adj[i][j])
89 ++in[j];
90 }
91 }
92 }
93
94 int
95 main(int argc, char **argv)
96 {
97 int i;
98 char str[MAX_NUM];
99 while(scanf("%d %d", &n, &m)!=EOF) {
100 for(i=0; i<n; i++)
101 scanf("%s", map[i]);
102 build_graph();
103 memset(str, 0, sizeof(str));
104 memset(visited, 0, sizeof(visited));
105 topological_sort(str, 0);
106 }
107 }