原来这道题目这么简单，记得当年高中的时候做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