USACO Cryptcowgraphy

本题基本算法为DFS，但要求编程者具备一定的“剪枝”能力。本人最初写的程序仅通过5个测试点，第6个数据始终不出解。于是看了NOCOW上的解答，加上了一个限制条件，就通过了所有数据，耗时最长仅0.8s。

可以从下面几个方面优化：
1）读入数据后，先检查C，O，W个数是否相等，输入串其他字符个数是否和目标串一致。
2）然后检查第一个C前面的字符是否与目标串一致，如果一致则在输入串和目标串中同时删去这一部分（它们已经不需要了）。对于最后一个W后的字符，采取相同操作。
3）在DFS扩展节点时对新产生节点执行2）操作，不过不要删除，否则回溯时要复原很麻烦。
4）用散列表记录访问过的节点（字符串），以免重复。不用散列表也可以通过所有数据，只不过最后两个数据耗时会超过1s。
5）如果一个串可以被复原，那么其中任意相邻两个在“COW”中的字符之间的串必须也是目标串的字串。（这个剪枝很强大）
6）先搜索'O'的位置，然后再确定'C'和'W'。（NOCOW上有人推荐的，使用后并不见得有什么效果）。

此外，USACO还给出了这个优化方案：
用链表而不是用数组存储字符串，这样变幻字符串可以方便一些。

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define HASH_TABLE_LENGTH 100007
005
006 typedef struct HNode
007 {
008     char str[80];
009     struct HNode * next;
010 }HNode;
011
012 char target[] = "Begin the Escape execution at the Break of Dawn";
013 int tlen;  //length of the target string
014 char input[80];
015 struct HNode *hashtable[HASH_TABLE_LENGTH];
016
017 int t;
018
019 void unable()
020 {
021     printf("0 0\n");
022     fclose(stdout);
023     exit(0);
024 }
025
026 void first_check()
027 {
028     int cnt[128];
029     int flag;
030     char *p;
031     memset(cnt,0,sizeof(cnt));
032     for(p = input;*p;p ++)
033         cnt[(int)*p] ++;
034
035     for(p = target;*p;p ++)
036         cnt[(int)*p] --;
037     int i;
038     for(i = flag = 0;i < 128;i ++)
039     {
040         if(i == 'C' || i == 'O' || i == 'W')    continue;
041         else
042         {
043             if(cnt[i] != 0)    flag = 1;
044         }
045     }
046     if(flag || cnt['C'] != cnt['O'] || cnt['O'] != cnt['W'] || cnt['W'] != cnt['C'])
047     {
048         unable();
049     }
050     else
051     {
052         t = cnt['C'];
053     }
054 }
055
056 void clean()   //further verify and remove the same head string in both target and input.
057 {
058     int i;
059     int olen,ilen;
060     olen = strlen(target);
061     ilen = strlen(input);
062     for(i = 0;i < olen;i ++)
063     {
064         if(input[i] == 'C')
065         {
066             memmove(input,input + i,ilen - i);   //remove chars before the first 'C'
067             memmove(target,target + i,olen - i);
068             olen = olen - i;     //recalculate string length
069             ilen = ilen - i;
070             break;
071         }
072         else if(input[i] != target[i])
073             unable();
074     }
075     for(i = 1;i <= olen;i ++)
076     {
077         if(input[ilen - i] == 'W')    //remove chars after the last 'W'
078         {
079             break;
080         }
081         else
082         {
083             if(input[ilen - i] != target[olen - i])
084                 unable();
085             input[ilen - i] = target[olen - i] = 0;
086         }
087     }
088     //puts(target);
089     //puts(input);
090 }
091
092 unsigned long StrHash(char *s)
093 {
094     unsigned long res = 0;
095     for(;*s;s ++)
096         res = (res + *s * 13) % HASH_TABLE_LENGTH;
097     return res;
098 }
099
100 int exist(char *s)   //if a string is already in table
101 {
102     unsigned long h = StrHash(s);
103     HNode *p;
104     for(p = hashtable[h];p != NULL;p = p->next)
105     {
106         if(strcmp(s,p->str) == 0)    return 1;
107     }
108     return 0;
109 }
110
111 void insert(char *s)   //add new string
112 {
113     unsigned long h = StrHash(s);
114     HNode *p;
115     p = malloc(sizeof(HNode));
116     strcpy(p->str,s);
117     p->next = hashtable[h];
118     hashtable[h] = p;
119 }
120
121 void decode_success()
122 {
123     printf("1 %d\n",t);
124     fclose(stdout);
125     exit(0);
126 }
127
128 int possible(char *s,int len)  //check whether string is possible to be converted to target, discard hopeless strings
129 {
130     int i;
131     for(i = 0;i < len;i ++)
132     {
133         if(s[i] == 'C')
134             break;
135         else if(s[i] != target[i])
136             return 0;
137     }
138     for(i = 1;i <= len;i ++)
139     {
140         if(s[len - i] == 'W')
141             break;
142         else    if(s[len - i] != target[tlen - i])
143             return 0;
144     }
145     int j = 0;
146     char tmp[80];
147     memset(tmp,0,sizeof(tmp));
148     for(i = 0;i < len;i ++)
149     {
150         if(s[i] == 'C' ||s[i] == 'W' || s[i] == 'O')
151         {
152             if(strstr(target,tmp) == NULL)    return 0;
153             memset(tmp,0,sizeof(tmp));
154             j = 0;
155         }
156         else
157         {
158             tmp[j] = s[i];
159             j ++;
160         }
161     }
162     return 1;
163 }
164
165 void solve(char *s,int len,int left)
166 {
167     if(left == 0)
168     {
169         if(strcmp(s,target) == 0)
170             decode_success();
171         return;
172     }
173     int c,o,w;
174     char next[80];
175     for(o = 0;o < len;o ++)
176     {
177         if(s[o] == 'O')
178         for(c = 0;c < o;c ++)
179         {
180             if(s[c] == 'C')
181             for(w = len - 1;w > o;w --)
182             {
183                 if(s[w] == 'W')     //create next string
184                 {
185                     memset(next,0,80);
186                     strncpy(next,s,c);
187                     strncat(next,s + o + 1,w - o - 1);
188                     strncat(next,s + c + 1,o - c - 1);
189                     strcat(next,s + w + 1);
190                     if(possible(next,len - 3) && !exist(next))
191                     {
192                         insert(next);
193                         //printf("%d %s\n",left,next);
194                         solve(next,len - 3,left - 1);
195                     }
196                 }
197             }
198         }
199     }
200 }
201
202 int main()
203 {
204     freopen("cryptcow.in","r",stdin);
205     freopen("cryptcow.out","w",stdout);
206     fgets(input,78,stdin);
207     input[strlen(input) - 1] = 0;
208     first_check();
209     clean();
210     tlen = strlen(target);
211     solve(input,strlen(input),t);
212     unable();
213     return 0;
214 }