0%

POJ 2362：Square DFS剪枝

发表于 分类于 Valine：

状态定义有时要服务于剪枝策略

题目链接

http://poj.org/problem?id=2362

题意

输入M个棍子(\(4\le M\le 20\))，问这M个棍子是否能首尾相接形成一个正方形。

题解

本质就是找一个数组的全排列，使得从头到尾能形成4段长度相等的区域。

由于只需找到一个符合条件的排列，想到直接使用DFS。

如果直接暴力搜索，复杂度是\(O(n!)\)的，显然会爆。必然需要剪枝。

定义stick[M]数组为：所有木棍及其长度。

搜索状态的定义

基本的状态

假设木棍总长度为target，则正方形边长是side = target / 4。

如果存在某个排列，那么在搜索到这个排列的过程中，应该有5个阶段：

  • 已组建完成0条边
  • 已组建完成1条边
  • 已组建完成2条边
  • 已组建完成3条边
  • 已组建完成4条边

因此，在状态描述中，必须有已经完成多少条边这一状态，记为finished_side

然后考虑上述每个阶段，都有一个当前边已有的长度这一状态，记为len

（其实上述两种状态可以使用当前的总长度sum来表示，sum % side表示len，sum / side表示已经完成多少边，为清晰期间，还是分成两个量表示）

visit数组标记已用过的木棍，用于表示当前状态下，还可以使用哪些木棍扩展子节点(visit值为false的点)

服务于剪枝的状态

按道理来说，以上三个状态已经足够完成搜索了，但是如果仅仅这样搜索的话，无法完全支持后续的剪枝策略。这里引入另一个状态描述——当前状态下，用于构建子节点的木棍的起始下标，记为start_index。

为何引入这个状态，在下文剪枝策略中描述。

剪枝策略

首先是全局的判断（甚至称不上是剪枝）

  • 总长度不为4的倍数，肯定不行··废话··
  • 最长的棍子大于边长，肯定不行

然后几个重点的剪枝策略：

  • 当finished_side == 3时，就可直接判断为可行了，因为只要总长度是4的倍数，最后一条边一定能构建成功
  • 构建某条边时，如果长度等于fail_length的木棍构建正方形失败，那么所有长度为fail_length的木棍都不能用于构建 ====> 剪去了在相同的长度木棍下重复搜索（也就是，每种长度的棍子，只需做一次拓展）
    • 这里为了判断方便，可以事先将棍子排序，让相同长度的都在一起
  • 如果本状态构造的边和父状态构造的边时同一条边，则只需扩展本状态后面（这里的“后面”指stick数组中）的木棍。
    • 这里解释了start_index这个状态存在的意义
    • 每次扩展子状态i之前，判断是否开启了一条新边：如果不是，则子状态的扩展起点只需在后面即可（start_index=i +1）；如果是，则扩展起点需重置为0(start_index=0)。

对最后一个剪枝策略的正确性作一个证明：

在构建同一条边的情况下，当前木棍(下标记做i)的前面的木棍(下标记做k)(k < i)，无非两种状态：

  • 已经被选择了，visit[k]值为true。这样的话，本来就不该选
  • 未被选择，visit[k]值为false。按照不剪枝的策略，木棍k本来是要被用来扩展子节点的，为什么不呢？
    • 由于每次都是按照stick数组的从前到后的顺序扩展的，k肯定在当前节点i的某个祖先节点扩展子节点时，曾经被选中过。且当时选中之后，k也曾把i拿去用于扩展子节点（即，选k又选i的情况，早就出现过了）。但显然那种情况是不可行的，否则早就成功返回了。因此，选择k肯定是不可行的。

但是当不是构建同一条边的时候，就应该从0开始重新找了。直观地看，构建上一条边舍弃的某些木棍，可能可以用于构建下一条边。

AC代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstring> 
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
using namespace std; 
typedef long long ll; 

int stick[25];
bool visit[25];
int target = 0;
int side = 0;
int M;

bool dfs(int start_index, int finished_side, int len) {
    if (finished_side == 3) {
        return true;
    }
    
    int last = -1;
    for (int i = start_index; i < M; i++) {
        // 如果 访问过/太长了/跟上次失败的一样长 就剪枝
        if (visit[i] || stick[i] + len > side || stick[i] == last) {
            continue;
        }

        visit[i] = true; // 开始扩展i节点, 标记visit数组
        // 正好开启下一条边
        if (stick[i] + len == side) {
            if (dfs(0, finished_side + 1, 0)) {  // 下次的start_index = 0
                return true;
            }
        }
        // 还是同一条边
        else {
            // 下次的start_index为i + 1
            if (dfs(i + 1, finished_side, len + stick[i])) {
                return true;
            }
        }
        last = stick[i];
        visit[i] = false; // 到达这里，说明上述的扩展不可行，恢复visit数组
    }
    return false;
}


bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &M);
        target = 0;
        int mmax = -1;
        for (int i = 0; i < M; i++) {
            scanf("%d", stick + i);
            target += stick[i];
            mmax = max(mmax, stick[i]);
        }
        
        if (target % 4) {
            puts("no");
            continue;
        }
        side = target / 4;
		if (mmax > side) {
            puts("no");
            continue;
        }
        memset(visit, false, sizeof(visit));
        sort(stick, stick + M, cmp);
        if (dfs(0, 0, 0)) { // 初始: 从0开始扩展、完成0条边、当前长度为0
            puts("yes");
        }
        else {
            puts("no");
        }
    }
    return 0;
}