USACO Snail Trail

一开始想复杂了，甚至拿来建图。其实直接用DFS模拟蜗牛的路径就可以了。貌似DFS效率并不是很低，最长耗时不过0.02s。

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04
05 int N;
06 int map[125][125];
07 int dx[4] = {0,0,-1,1};
08 int dy[4] = {1,-1,0,0};
09 int max;
10
11 void init()
12 {
13     int B,i;
14     char c;
15     scanf("%d%d\n",&N,&B);
16     while(B --)
17     {
18         scanf("%c%d\n",&c,&i);
19         map[i][(int)(c - 'A' + 1)] = 1;
20     }
21     for(i = 0;i <= N + 1;i ++)  //borders as blocks
22         map[0][i] = map[N + 1][i] = map[i][0] = map[i][N + 1] = 1;
23 }
24
25 int visit[125][125] = {};
26
27 void dfs(int i,int j,int step,int d)
28 {
29     if(step > max)    max = step;
30     if(map[i + dx[d]][j + dy[d]] == 1)  //block ahead, change direction
31     {
32         if(d <= 1)
33         {
34             int k;
35             for(k = 2;k <= 3;k ++)
36             if(map[i + dx[k]][j + dy[k]] == 0 && visit[i + dx[k]][j + dy[k]] == 0)
37             {
38                 visit[i + dx[k]][j + dy[k]] = 1;
39                 dfs(i + dx[k],j + dy[k],step + 1,k);
40                 visit[i + dx[k]][j + dy[k]] = 0;
41             }
42         }
43         if(d >= 2)
44         {
45             int k;
46             for(k = 0;k <= 1;k ++)
47             if(map[i + dx[k]][j + dy[k]] == 0 && visit[i + dx[k]][j + dy[k]] == 0)
48             {
49                 visit[i + dx[k]][j + dy[k]] = 1;
50                 dfs(i + dx[k],j + dy[k],step + 1,k);
51                 visit[i + dx[k]][j + dy[k]] = 0;
52             }
53         }
54     }
55     else
56     {
57         if(visit[i + dx[d]][j + dy[d]] == 0)   //go ahead
58         {
59             visit[i + dx[d]][j + dy[d]] = 1;
60             dfs(i + dx[d],j + dy[d],step + 1,d);
61             visit[i + dx[d]][j + dy[d]] = 0;
62         }
63     }
64 }
65
66 int main()
67 {
68     freopen("snail.in","r",stdin);
69     freopen("snail.out","w",stdout);
70     init();
71     memset(visit,0,sizeof(visit));
72     dfs(1,1,1,0);
73     memset(visit,0,sizeof(visit));
74     dfs(1,1,1,3);
75     printf("%d\n",max);
76     return 0;
77 }