USACO Wisconsin Squares

这是一道简单的搜索题目，用DFS即可解决。
代码如下

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 struct move
006 {
007     int i,j;
008     char cow;
009 }ans[16];
010
011 char arr[4][5];
012 char bak[4][5];
013 int mark[4][4];
014 int left[128];
015 int dx[9] = {0,0,1,1,1,-1,-1,-1,0};
016 int dy[9] = {1,-1,0,-1,1,1,0,-1,0};
017 long long count = 0;
018
019 void init()
020 {
021     int i;
022     for(i = 0;i < 4;i ++)
023         scanf("%s",arr[i]);
024     left['A'] = left['B'] = left['C'] = left['E'] = left['D'] = 3;
025     memcpy(bak,arr,sizeof(bak));
026 }
027
028 void pt()
029 {
030     int i;
031     for(i = 0;i < 16;i ++)
032         printf("%c %d %d\n",ans[i].cow,ans[i].i + 1,ans[i].j + 1);
033 }
034
035 int inmap(int i,int j)  //check if [i][j] in the range
036 {
037     if((i >= 0) && (i <= 3) && (j >= 0) && (j <= 3))    return 1;
038     return 0;
039 }
040
041 int valid(char c,int i,int j)
042 {
043     if(mark[i][j] == 1)    return 0;   //[i][j] is already arranged
044     int k;
045     for(k = 0;k < 9;k ++)
046     {
047         if(inmap(i + dx[k],j + dy[k]))
048         {
049             if(arr[(i + dx[k])][j + dy[k]] == c)    return 0;
050         }
051     }
052     return 1;
053 }
054
055 void dfs(int step)
056 {
057     if(step == 16)
058     {
059         if(count == 0)    pt();  //output the first solution
060         count ++;
061     }
062     char c;
063     int i,j;
064     for(c = 'A';c <= 'E';c ++)
065         if(left[(int)c] > 0)
066         {
067             left[(int)c] --;
068             for(i = 0;i < 4;i ++)
069             for(j = 0;j < 4;j ++)
070                 if(valid(c,i,j) == 1)
071                 {
072                     arr[i][j] = c;
073                     mark[i][j] = 1;
074                     ans[step].cow = c;
075                     ans[step].i = i;
076                     ans[step].j = j;
077                     dfs(step + 1);
078                     mark[i][j] = 0;
079                     arr[i][j] = bak[i][j];
080                 }
081             left[(int)c] ++;
082         }
083 }
084
085 int main()
086 {
087     freopen("wissqu.in","r",stdin);
088     freopen("wissqu.out","w",stdout);
089     int i,j;
090     init();
091     ans[0].cow = 'D';
092     for(i = 0;i < 4;i ++)   //move a 'D' first
093     for(j = 0;j < 4;j ++)
094     {
095         if(valid('D',i,j) == 1)
096         {
097             //printf("%d %d\n",i,j);
098             arr[i][j] = 'D';
099             mark[i][j] = 1;
100             ans[0].i = i;
101             ans[0].j = j;
102             dfs(1);
103             mark[i][j] = 0;
104             arr[i][j] = bak[i][j];
105         }
106     }
107     printf("%lld\n",count);
108     return 0;
109 }

起初本人的程序总是超时，最后发现第95行后多了一个';'————一个及其弱智的错误。

更另我惊讶的是，USACO上面只有一个测试数据，并且就是样例数据。