USACO Frame up

题意很简单：寻找一个可以构成输入图形的字符序列。

本人的解法：形象的说就是尝试把最上面的一层移除，然后不断重复，直到所有的层都被移除就得出了一个可行方案。这个想法可以用DFS实现，代码中possible函数用于判断某个字符是否能在当前的最上面，可以就移除它，进入下一层。这个算法有一个缺陷：得出的结果不是排序好的，因此需要先储存然后用qsort。

USACO的解法：先构建一个“图”，即用一个above[a][b]，表示两个字符代表的层之间的关系，若above[a][b] == 1，那么a一定在b上面。接着用DFS遍历就可以了。

本人一开始又被坑了，题目中有说：It is possible to see at least one part of each of the four sides of a frame. A corner is part of two sides.因此可以直接确定每个frame上下左右的边界。因此possible函数没必要像下面的代码中那样复杂，DFS中的4个for也可以省略。

丑陋的代码：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #include <ctype.h>
005
006 int H,W;
007 char map[30][31];
008 int minh[27],minw[27];   //minimum span of a layer
009 char secq[26];    //for dfs use
010 int used[128];    //for dfs use
011 int lcnt = 0;   //layer count
012 char cor[27];   //store num -> char for a little faster speed
013 char ans[10000][26];  //store answers
014 int anscnt = 0;
015 int charappcnt[128];   //count of chars, used in func possible
016 int row[128][31],col[128][31];   //mark if a char appears in a row/col
017
018 void init()
019 {
020     int i,j,m,n;
021     int d[128];
022     memset(d,0,sizeof(d));
023     scanf("%d%d\n",&H,&W);
024     for(i = 0;i < H;i ++)
025         scanf("%s\n",map[i]);
026     for(i = 0;i < H;i ++)
027         for(j = 0;j < W;j ++)
028             if(isupper(map[i][j]) && d[(int)map[i][j]] == 0)
029             {
030                 d[(int)map[i][j]] = 1;
031                 lcnt ++;
032             }
033     for(i = 'A',j = 0;i <= 'Z';i ++)
034     {
035         if(d[i] == 0)    continue;
036         cor[++ j] = (char)i;
037         int b,e;
038         int flag;
039         flag = 1;
040         for(m = 0;m < H && flag;m ++)
041             for(n = 0;n < W;n ++)    if(map[m][n] == i)    {b = m;flag = 0;break;}
042         flag = 1;
043         for(m = H - 1;m >= 0 && flag;m --)
044             for(n = 0;n < W;n ++)    if(map[m][n] == i)    {e = m;flag = 0;break;}
045         minh[j] = e - b;
046         flag = 1;
047         for(n = 0;n < W && flag;n ++)
048             for(m = 0;m < H;m ++)    if(map[m][n] == i)    {b = n;flag = 0;break;}
049         flag = 1;
050         for(n = W - 1;n >= 0 && flag;n --)
051             for(m = 0;m < H;m ++)    if(map[m][n] == i)    {e = n;flag = 0;break;}
052         minw[j] = e - b;
053         if(minw[j] == 0)    minw[j] = 2;
054         if(minh[j] == 0)    minh[j] = 2;
055     }
056     for(i = 0;i < H;i ++)
057         for(j = 0;j < W;j ++)
058         {
059             charappcnt[(int)map[i][j]] ++;
060             row[(int)map[i][j]][i] = 1;
061             col[(int)map[i][j]][j] = 1;
062         }
063 }
064
065 int possible(char c,int i,int j,int m,int n)
066 {
067     int k;
068     int count = 0;
069     for(k = i;k <= m;k ++)
070     {
071         if(map[k][j] != c && used[(int)map[k][j]] == 0)    return 0;
072         if(map[k][n] != c && used[(int)map[k][n]] == 0)    return 0;
073         if(map[k][j] == c)    count ++;
074         if(map[k][n] == c)    count ++;
075     }
076     for(k = j;k <= n;k ++)
077     {
078         if(map[i][k] != c && used[(int)map[i][k]] == 0)    return 0;
079         if(map[m][k] != c && used[(int)map[m][k]] == 0)    return 0;
080         if(map[i][k] == c && k != j && k != n)    count ++;
081         if(map[m][k] == c && k != j && k != n)    count ++;
082     }
083     if(count != charappcnt[(int)c])    return 0;
084     return 1;
085 }
086
087 void dfs(int curl)
088 {
089     int i,a,b,m,n;
090     if(curl < 0)
091     {
092         int i;
093         for(i = 0;i < anscnt;i ++)
094             if(strncmp(ans[i],secq,lcnt) == 0)    return;
095         strncpy(ans[anscnt ++],secq,lcnt);
096         return;
097     }
098     for(i = lcnt;i >= 1;i --)
099     {
100         if(!used[(int)cor[i]])
101         {
102             used[(int)cor[i]] = 1;
103             secq[curl] = cor[i];
104             for(a = 0;a < H;a ++)
105                 if(row[(int)cor[i]][a])
106                 for(b = 0;b < W;b ++)
107                     if(col[(int)cor[i]][b])
108                     for(m = a + minh[i];m < H;m ++)
109                         if(row[(int)cor[i]][m])
110                         for(n = b + minw[i];n < W;n ++)
111                         {
112                             if(col[(int)cor[i]][n] && possible(cor[i],a,b,m,n))
113                             {
114                                 dfs(curl - 1);
115                                 if(curl == 0)    goto lable;
116                             }
117                         }
118             lable:
119             secq[curl] = 0;
120             used[(int)cor[i]] = 0;
121         }
122     }
123 }
124
125 int cmp(const void *a,const void *b)
126 {
127     return strncmp((char *)a,(char *)b,lcnt);
128 }
129
130 int main()
131 {
132     int i;
133     freopen("frameup.in","r",stdin);
134     freopen("frameup.out","w",stdout);
135     init();
136     dfs(lcnt - 1);
137     qsort(ans,anscnt,26,cmp);
138     for(i = 0;i < anscnt;i ++)
139         printf("%s\n",ans[i]);
140     return 0;
141 }