原來這道題目這么簡單，記得當年高中的時候做USACO的時候，好像最后就是卡在這道題目上面，然后就是NOIP了
然后我就傷心的告別了NOIP投向了好好學習的懷抱。
今天拿過來看還是沒什么思路，然后就去搜了一下解題報告。
其實這個題目無論如何也是要DFS的，因為人家要你輸出全部的答案。這樣就不用怕了，最多就是剪剪枝。
但是最開始沒有想到這一點。
問題就在這個剪枝上，和怎么判斷合理的解上面。
方法就是，首先找到每一個Frame的四個角。
然后沿著這個Frame的每條邊走一下，如果有其他的字符，就是跟當前Frame不同的字符，那么這個字符肯定是在當前這個字符上層的。
這樣就能用一張表來確定上下關系，Above[i][j]，表示第i個字符在第j個字符上層
然后就是根據這張表來做一個DFS，這樣就可以了。
看了leokan的解題報告，說還要floyd一下。
這樣做的目的無非也就是想確定兩兩之間的上下層關系罷了。
但是似乎沒這個必要，直接DFS就可以了。
1 import java.io.*;
2 import java.util.*;
3 /*
4 ID: yanglei4
5 LANG: JAVA
6 TASK:frameup
7 */
8 public class frameup{
9 static char[][] board;
10 static int[][] pos;
11 static int[] in;
12 static int cnt;
13 static int[][] above;
14 static char[] answer;
15 static PrintWriter out;
16 public static void findAnswer(int step) {
17 int i,j;
18 if (step >= cnt) {
19 for (int k = 0; k < cnt; k++)
20 out.print(answer[k]);
21 out.println();
22 }
23 for (i = 0; i < 26; i++)
24 if (in[i]> 0) {
25 for (j = 0; j < 26; j++)
26 if (in[j] > 0 && above[i][j] == 1) break;
27
28 if (j >= 26) { /* no such frame, so this COULD be the next one */
29 answer[step] = (char) ('A' + i);
30 in[i] = 0; /* mark as in answer */
31 findAnswer(step + 1);
32 in[i] = 1; /* clear mark */
33 }
34
35 }
36 }
37 public static void main(String[] args) throws IOException {
38 BufferedReader f = new BufferedReader(new FileReader("frameup.in"));
39 out = new PrintWriter(new BufferedWriter(new FileWriter("frameup.out")));
40 StringTokenizer st = new StringTokenizer(f.readLine());
41 int H = Integer.parseInt(st.nextToken());
42 int W = Integer.parseInt(st.nextToken());
43
44 board = new char[30][32];
45 pos = new int[26][4];
46 in = new int[26];
47 cnt = 0;
48
49 above = new int[26][26];
50 answer = new char[27];
51
52 for (int i = 0; i < H; i++) {
53 String temp = f.readLine();
54 board[i] = temp.toCharArray();
55 for (int j = 0; j < W; j++) {
56 if (board[i][j] != '.') {
57 int loc = board[i][j] - 'A';
58
59 if (in[loc] == 0) {//First time met
60 in[loc] = 1;
61 cnt++;
62 pos[loc][0] = pos[loc][2] = i;
63 pos[loc][1] = pos[loc][3] = j;
64 }
65 else {
66 if (i < pos[loc][0]) pos[loc][0] = i;
67 if (i > pos[loc][2]) pos[loc][2] = i;
68 if (j < pos[loc][1]) pos[loc][1] = j;
69 if (j > pos[loc][3]) pos[loc][3] = j;
70 }
71
72 }
73 }
74 }
75
76 for (int i = 0; i < 26; i++)
77 if (in[i] > 0) { /* for each frame */
78 for (int j = pos[i][0]; j <= pos[i][2]; j++) { /* check left and right borders */
79
80 /* left */
81 int loc = board[j][pos[i][1]] - 'A';
82 if (loc != i) /* there's a different frame where this one should be */
83 above[loc][i] = 1; /* that different frame must be above this one */
84
85 /* right */
86 loc = board[j][pos[i][3]] - 'A';
87 if (loc != i) /* same as left */
88 above[loc][i] = 1;
89 }
90 for (int j = pos[i][1]; j <= pos[i][3]; j++) { /* check top and bottom */
91
92 /* top */
93 int loc = board[pos[i][0]][j] - 'A';
94 if (loc != i)
95 above[loc][i] = 1;
96
97 /* bottom */
98 loc = board[pos[i][2]][j] - 'A';
99 if (loc != i)
100 above[loc][i] = 1;
101 }
102 }
103
104 findAnswer(0);
105 out.close();
106 System.exit(0);
107 }
108 }
109