Posted on 2008-06-16 14:20
superman 閱讀(607)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1083 C++ 00:00.01 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m;
7 char pic[30][30];
8
9 int in[26];
10 bool map[30][30];
11
12 struct { int ax, ay, bx, by; } frame[26];
13 int FrameCnt;
14
15 bool choosed[26];
16 char ans[26];
17
18 void TopSort(int k)
19 {
20 if(k == FrameCnt)
21 {
22 for(int i = 0; i < FrameCnt; i++)
23 cout << char(ans[i] + 'A');
24 cout << endl;
25 return;
26 }
27
28 for(int i = 0; i < FrameCnt; i++)
29 if(in[i] == 0 && choosed[i] == false)
30 {
31 ans[k] = i;
32
33 for(int j = 0; j < FrameCnt; j++)
34 if(map[i][j])
35 in[j]--;
36
37 choosed[i] = true;
38 TopSort(k + 1);
39 choosed[i] = false;
40
41 for(int j = 0; j < FrameCnt; j++)
42 if(map[i][j])
43 in[j]++;
44 }
45 }
46
47 int main()
48 {
49 while(cin >> n >> m)
50 {
51 memset(in, 0, sizeof(in));
52 memset(pic, false, sizeof(pic));
53 memset(map, false, sizeof(map));
54 memset(choosed, false, sizeof(choosed));
55
56 bool appear[26] = { false };
57
58 for(int i = 0; i < n; i++)
59 for(int j = 0; j < m; j++)
60 {
61 cin >> pic[i][j];
62 if(pic[i][j] == '.')
63 pic[i][j] = -1;
64 else
65 {
66 pic[i][j] -= 'A';
67 appear[pic[i][j]] = true;
68 }
69 }
70
71 FrameCnt = 0;
72 for(int i = 0; i < 26; i++)
73 FrameCnt += appear[i];
74
75 for(int k = 0; k < FrameCnt; k++)
76 {
77 bool x;
78
79 x = false;
80 for(int i = 0; i < n; i++) {
81 for(int j = 0; j < m; j++)
82 if(pic[i][j] == k) {
83 frame[k].ax = i; x = true; break;
84 }
85 if(x) break;
86 }
87
88 x = false;
89 for(int j = 0; j < m; j++) {
90 for(int i = 0; i < n; i++)
91 if(pic[i][j] == k) {
92 frame[k].ay = j; x = true; break;
93 }
94 if(x) break;
95 }
96
97 x = false;
98 for(int i = n - 1; i >= 0; i--) {
99 for(int j = m - 1; j >= 0; j--)
100 if(pic[i][j] == k) {
101 frame[k].bx = i; x = true; break;
102 }
103 if(x) break;
104 }
105
106 x = false;
107 for(int j = m - 1; j >= 0; j--) {
108 for(int i = n - 1; i >= 0; i--)
109 if(pic[i][j] == k) {
110 frame[k].by = j; x = true; break;
111 }
112 if(x) break;
113 }
114 }
115
116 for(int k = 0; k < FrameCnt; k++)
117 {
118 int i, j;
119
120 i = frame[k].ax;
121 for(j = frame[k].ay; j <= frame[k].by; j++)
122 if(pic[i][j] != k)
123 map[k][pic[i][j]] = true;
124
125 i = frame[k].bx;
126 for(j = frame[k].ay; j <= frame[k].by; j++)
127 if(pic[i][j] != k)
128 map[k][pic[i][j]] = true;
129
130 j = frame[k].ay;
131 for(i = frame[k].ax; i <= frame[k].bx; i++)
132 if(pic[i][j] != k)
133 map[k][pic[i][j]] = true;
134
135 j = frame[k].by;
136 for(i = frame[k].ax; i <= frame[k].bx; i++)
137 if(pic[i][j] != k)
138 map[k][pic[i][j]] = true;
139 }
140
141 for(int i = 0; i < FrameCnt; i++)
142 for(int j = 0; j < FrameCnt; j++)
143 if(map[i][j])
144 in[j]++;
145
146 TopSort(0);
147 }
148
149 return 0;
150 }
151