Solve

USACO 5.4.4 Betsy

题目解答

问题的本质是求所有的可能的哈密顿路径的情况，可以使用DFS+剪枝求解。
本问题的考点也是剪枝，有以下两种情况：

  1. 孤立区域的形成:
    如图所示，孤立区域也就是被划分成了两个域的情况，这个时候无论走哪个区域另一个区域都无法访问，那么一个剪枝就可以是判断当前有无孤立区域的形成，这个产生条件比较多，有一种基本情况就是如果当前点上下（包括边界）被访问过了，而左右没被访问则必产生孤立，另一个情况则正好相反。理由是当前点上下如果被访问了，而这两个访问过的点都是由起点走过来的，也就是都连通到起点，意义就是这两个点本身是连通的。我们不能穿过被访问过的路径走交叉路线，所以说这样无论走哪里都会被包住再也出不来了。这是一个情况。

  2. 进入死胡同:
    我们考虑类似围棋中的气，每个格子不需要一进一出，也就是至少有两个度，如果只有一个度则走进去后就再也出不来了，我们不必要碰到度为一的点再去回溯。而是一开始就避免度为一的点产生。剪枝方式是：除去起点和终点外如果当前点的周围未被访问的格子中有度为一的点(也就是连通到另外一个未被访问的格子)，那么这个点必须要访问，理由是这个点如果被访问，就相当于他的一个入度被利用了，如果不访问则就浪费掉了。浪费之后他的度为1，以后则会只进不出。因此必须要访问，所以可以推出另一个关于度的剪枝，如果存在两个以上的度为1的点则回溯，因为不能两个同时都选，选了一个，另一个必然是死胡同。

各种情况

运行情况

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.000 secs, 3376 KB]
Test 2: TEST OK [0.000 secs, 3376 KB]
Test 3: TEST OK [0.000 secs, 3376 KB]
Test 4: TEST OK [0.000 secs, 3376 KB]
Test 5: TEST OK [0.000 secs, 3376 KB]
Test 6: TEST OK [0.000 secs, 3376 KB]
Test 7: TEST OK [0.119 secs, 3376 KB]

All tests OK.

YOUR PROGRAM (‘betsy’) WORKED FIRST TIME! That’s fantastic
– and a rare thing. Please accept these special automated
congratulations.

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
 
using namespace std;
 
bool map[9][9];
int pos[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, n, total;
 
inline int getlive(int x, int y){
        int t = 0;
        for(int k = 0; k < 4; k++)
                if(!map[x + pos[k][0]][y + pos[k][1]])
                        t++;
        return t;
}
 
void dfs(int x, int y, int sum){
        if(x == n && y == 1){    //剪枝1,不能提前到达终点
                if(sum == n * n) total++;
                return;
        }
        if((map[x][y-1] && map[x][y+1] && !map[x-1][y] && !map[x+1][y]) || 
           (!map[x][y-1] && !map[x][y+1] && map[x-1][y] && map[x+1][y])) //剪枝2，孤立区域剪枝
                return;
        int mx, my, count = 0;
        for(int i = 0; i < 4; i++){               //剪枝3,格子的度的处理      
                int X = x + pos[i][0], Y = y + pos[i][1];
                if(map[X][Y] || (X == n && Y == 1)) continue;
                if(getlive(X, Y) < 2) count++, mx = X, my = Y;
        }
        if(count > 1) return;
        else{
                if(count == 1){
                        map[mx][my] = 1;
                        dfs(mx, my, sum + 1);
                        map[mx][my] = 0;
                }
                else
                        for(int i = 0; i < 4; i++){
                                int X = x + pos[i][0], Y = y + pos[i][1];
                                if(!map[X][Y]){
                                        map[X][Y] = 1;
                                        dfs(X, Y, sum + 1);
                                        map[X][Y] = 0;
                                }
                        }
        }
}
 
int main(){
        cin >> n;
        for(int i = 1; i <= n; i++)       //处理边界
                map[1][1] = map[0][i] = map[n + 1][i] = map[i][0] = map[i][n + 1] = 1;
        dfs(1, 1, 1); 
        cout << total << endl;
        return 0;
}

注意事项

剪枝的消耗也要考虑在内。

难易等级

Medium Up(NOIP the 4th)

其他方法

基于SCC的状态压缩动态规划，参考陈丹琦集训队论文。

后记

本文是原Wordpress博客的移植，附：全部USACO题目解答。