USACO The Primes

DFS是这道题的基本算法，虽然只有25个空，不过题目要求输出所有结果，如果一行一行的填，是必定超时的（某些数据要10s+才有结果）。

这道题的关键就在合理安排搜索顺序，本人是这样搜索的（图中数字分别对应每个solve函数）：

0    3    0    3    0
1    0    2    0    1
4    4    0    4    4
1    0    2    0    1
0    3    0    3    0

虽然上面这种顺序不是最快的，但是都可以在0.4s内出结果。当然，USACO的Analysis中有速度更快的顺序安排方案，不过代码比较繁琐。

不过，改变搜索顺序会带来一个小问题——给出的结果不是排序的。幸好，stdlib里面有qsort，先把搜索结果储存起来，排序后输出就好了。

从这个题目可以明显看出，DFS时，搜索顺序尤其重要，尤其在缺乏其他剪枝策略的时候。把可以制造较多限制的对象放在搜索树的上面，可以起到很好的作用。从广义上讲，这也算一种剪枝了。

代码如下，比较丑陋。

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 struct node
006 {
007     long line[5];
008 }ans[1000];
009
010 _Bool isprime[100000];
011 long prime[1000];
012 int prime_digit[1000][5];
013 long totprime;
014
015 int board[5][5];
016 int leftsum[5];
017
018 int ans_cnt = 0;
019 int sum,first;
020
021 int cmp(const void *v1,const void *v2)  //for qsort use
022 {
023     int i;
024     struct node *a,*b;
025     a = (struct node *)v1;
026     b = (struct node *)v2;
027     for(i = 0;i < 5;i ++)
028     {
029         if(a->line[i] > b->line[i])
030             return 1;
031         else if(a->line[i] < b->line[i])
032             return -1;
033     }
034     return 0;
035 }
036
037 void store_ans()  //change board into five longints and store them in ans array
038 {
039     int i,j;
040     for(i = 0;i < 5;i ++)
041         for(j = 0;j < 5;j ++)
042         {
043             ans[ans_cnt].line[i] *= 10;
044             ans[ans_cnt].line[i] += board[i][j];
045         }
046     ans_cnt ++;
047 }
048
049 void separate(long num,int *arr)
050 {
051     int i;
052     for(i = 4;i >= 0;i --)
053     {
054         *(arr + i) = num % 10;
055         num /= 10;
056     }
057 }
058
059 int digit_sum(long num)
060 {
061     int s = 0,i;
062     for(i = 0;i < 5;i ++)
063     {
064         s += num % 10;
065         num /= 10;
066     }
067     return s;
068 }
069
070 void calc_primes()
071 {
072     long k,i;
073     for(i = 2;i < 100000;i ++)
074         isprime[i] = 1;
075     //filter
076     for(i = 2;i < 100000;i ++)
077         if(isprime[i])
078             for(k = 2;k * i < 100000;k ++)
079                 isprime[k * i] = 0;
080     totprime = 0;
081     for(i = 0;i < 10000;i ++)  //do not forget this
082         isprime[i] = 0;
083     for(i = 10000;i < 100000;i ++)
084     {
085         if(isprime[i] && digit_sum(i) == sum)
086         {
087             separate(i,prime_digit[totprime]);  //store primes we may need
088             prime[totprime] = i;
089             totprime ++;
090         }
091         else    isprime[i] = 0;
092     }
093 }
094
095 long combine(int a,int b,int c,int d,int e)
096 {
097     return (10000 * (long)a + 1000 * (long)b + 100 * (long)c + 10 * (long)d + (long)e);
098 }
099
100 void solve4(int c)  //complete the middle line and check whether the board satisfies the constraints
101 {
102     if(c == 2)    c ++;
103     if(c >= 5)
104     {
105         if(isprime[combine(board[2][0],board[2][1],board[2][2],board[2][3],board[2][4])])
106             store_ans();
107         return;
108     }
109     int rem;
110     rem = sum - board[0][c] - board[1][c] - board[3][c] - board[4][c];
111     if(rem >= 0 && isprime[combine(board[0][c],board[1][c],rem,board[3][c],board[4][c])])
112     {
113         board[2][c] = rem;
114         solve4(c + 1);
115         board[2][c] = 0;
116     }
117 }
118
119 void solve3(int l)  //fill in the top and bottom line
120 {
121     int i,rem;
122     if(l >= 5)
123     {
124         solve4(0);
125     }
126     for(i = 0;i <= 9;i ++)
127     {
128         rem = sum - i - board[l][0] - board[l][2] - board[l][4];
129         if(rem >= 0 && isprime[combine(board[l][0],i,board[l][2],rem,board[l][4])])
130         {
131             board[l][1] = i;
132             board[l][3] = rem;
133             solve3(l + 4);
134             board[l][1] = board[l][3] = 0;
135         }
136     }
137 }
138
139 void solve2() //fill in the middle column
140 {
141     int i,rem;
142     for(i = 1;i <= 9;i ++)
143     {
144         rem = sum - board[1][2] - board[2][2] - board[3][2] - i;
145         if(rem > 0 && isprime[combine(i,board[1][2],board[2][2],board[3][2],rem)])
146         {
147             board[0][2] = i;
148             board[4][2] = rem;
149             solve3(0);
150             board[0][2] = board[4][2] = 0;
151         }
152     }
153 }
154
155 void solve1(int depth)//fill in the 2nd and 4th line
156 {
157     if(depth == 2)
158     {
159         solve2();
160         return;
161     }
162     int l,rem;
163     int i,j;
164     if(depth == 0)    l = 1;
165     if(depth == 1)    l = 3;
166     for(i = 1;i <= 9;i ++)
167     {
168         board[l][0] = i;
169         for(j = 0;j <= 9;j ++)
170         {
171             board[l][2] = j;
172             rem = sum - board[l][0] - board[l][1] - board[l][2] - board[l][3];
173             if(rem > 0 && isprime[combine(board[l][0],board[l][1],board[l][2],board[l][3],rem)])
174             {
175                 board[l][4] = rem;
176                 solve1(depth + 1);
177                 board[l][4] = 0;
178             }
179             board[l][2] = 0;
180         }
181         board[l][0] = 0;
182     }
183 }
184
185 int main()
186 {
187     freopen("prime3.in","r",stdin);
188     freopen("prime3.out","w",stdout);
189     scanf("%d %d",&sum,&first);
190     calc_primes();
191     int i,j,lv;
192     board[0][0] = first;
193     //fill in the diagonals first
194     for(i = 0;i < totprime;i ++)
195     {
196         if(prime_digit[i][0] == first)
197         {
198             for(lv = 1;lv < 5;lv ++)
199                 board[lv][lv] = prime_digit[i][lv];
200
201             for(j = 0;j < totprime;j ++)
202             {
203                 if(prime_digit[j][2] == board[2][2])
204                 {
205                     board[4][0] = prime_digit[j][0];
206                     board[3][1] = prime_digit[j][1];
207                     board[1][3] = prime_digit[j][3];
208                     board[0][4] = prime_digit[j][4];
209                     solve1(0);
210                 }
211             }
212         }
213     }
214     //sort the solutions and then output them
215     qsort(ans,ans_cnt,sizeof(struct node),cmp);
216     for(i = 0;i < ans_cnt;i ++)
217     {
218         if(i != 0)    printf("\n");
219         for(j = 0;j < 5;j ++)
220         {
221             printf("%ld\n",ans[i].line[j]);
222         }
223     }
224     fclose(stdout);
225     fclose(stdin);
226     return 0;
227 }