USACO Betsy's Tour

算法很明显——DFS：从（1,1）点开始，向四个方向行走，每个点最多走一次，直到走到（N，1）点，并且总步数恰好等于N * N - 1。
可是，当N=7时，上面的算法要耗费好几分钟的时间。

有下面几种剪枝的方法（英文的是USACO提供的，本人用了加*号的）：

• If we use an array with a sentinel-buffer(哨兵) around the edges, we can avoid extra complexity introduced by further optimizations. Some speed is gained, too.(*)
• If we keep a running sum of the total number of squares touched in each column and in each row, we can check whether we have created a "wall" between the market and our current position, and prune these states.
• If we ever reach the right-hand wall at a distance vertically of Y without having touched the square at Y-1, we know we have created a wall in some shape that separates our current position with the square at Y-1. The same holds for every wall.
• keep track of the number of neighbor-squares that have been touched at each square. Each time we touch a square, we increment its neighbors' neighbor-sum. When a sum reaches 3, we know that we can stop because there is now a dead end at that square (unless we are going to that square next.) （这个剪枝很强大，不过我没有使用）
• 如果发现DFS当前到达点相邻的一个不是终点的点，其周围的点都被访问了，那么继续往下走就会形成一个永远无法到达的孤点，所以直接return。(*)
• 当前点左右都是已经点(包括边缘)，而上下都是未经点时，一定会有孤立的区域，return。同理，当前点上下都是已经点(包括边缘)，而左右都是未经点时，return。（来源于NOCOW）（*）

组合使用几个剪枝后，就可以很快的通过N=7的情况了，在USACO的机器上只要0.355s.

据说这道题还可以用“基于连通性的状态压缩动态规划”做，NOCOW上有代码。

本人的代码：

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

01 #include
02 #include
03
04 int N;
05 long cnt = 0;
06 int map[10][10] = {};
07 int dx[4] = {0,0,1,-1};
08 int dy[4] = {1,-1,0,0};
09
10 int isdest(int x,int y)
11 {
12     if(x == N && y == 1)    return 1;
13     return 0;
14 }
15
16 int checkaround(int x,int y)  //count way
17 {
18     int i;
19     int c = 0;
20     for(i = 0;i < 4;i ++)
21         if(map[x + dx[i]][y + dy[i]] == 0)
22             c ++;
23     return c;
24 }
25
26 void dfs(int x,int y,int d)
27 {
28     if(isdest(x,y))
29     {
30         if(d < N * N - 1)    return;
31         cnt ++;
32         return;
33     }
34     int k,nx,ny;
35     int mustcnt = 0,mustk;
36     if(map[x + 1][y] && map[x - 1][y] && !map[x][y - 1] && !map[x][y + 1])    return;
37     if(!map[x + 1][y] && !map[x - 1][y] && map[x][y - 1] && map[x][y + 1])    return;
38     for(k = 0;k < 4;k ++)
39     {
40         nx = x + dx[k];
41         ny = y + dy[k];
42         if(map[nx][ny] == 0)
43         {
44             if(!isdest(nx,ny) && checkaround(nx,ny) == 0)   //no way around new node,so it is an orphan node
45                 return;
46             if(!isdest(nx,ny) && checkaround(nx,ny) == 1)
47             {
48                 map[nx][ny] = 1;
49                 dfs(nx,ny,d + 1);
50                 map[nx][ny] = 0;
51                 return;
52             }
53                 map[nx][ny] = 1;
54                 dfs(nx,ny,d + 1);
55                 map[nx][ny] = 0;
56         }
57     }
58 }
59
60 void init()
61 {
62     int i,j;
63     for(i = 0;i <= N + 1;i ++)
64         for(j = 0;j <= N + 1;j ++)
65             map[i][j] = 1;
66     for(i = 1;i <= N;i ++)
67         for(j = 1;j <= N;j ++)
68             map[i][j] = 0;
69 }
70
71 int main()
72 {
73     freopen("betsy.in","r",stdin);
74     freopen("betsy.out","w",stdout);
75     scanf("%d",&N);
76     init();
77     map[1][1] = 1;
78     dfs(1,1,0);
79     printf("%ld\n",cnt);
80     return 0;
81 }