是一道启发式搜索和位运算，剪枝的杂合题目。
要学好搜索，搜索是很重要的算法。那些很厉害的选手都是搜索打得好的。(By Instructor Li)
题目分析
-
首先，(N≤5)，且边数是(2N(N+1)≤60)。在这样的小数据下可以位运算优化。
-
启发式搜索，设计估价函数(G(X))。要求低于真实代价。下面是一种方法：
-
对于每一个正方形，删除它的所有边。重复这个操作知道没有正方形。操作的次数就是估价
-
然而，仅仅这样不足以过掉这题。还需要优化。
判断正方形
-
在纸上推导一下，或者直接找规律，可以得到：
-
如果一条横放的火柴编号为(X_0)，
-
(X_0)左下方的(L)根火柴分别是：$ X_i=X + (2i-1) N + i - 1,(0<i<L)$。
-
那么正方形的左边界确定了，右边界的编号就是左边界加上边长。
-
预处理出所有的正方形，并且按照从小到大的顺序。原因后面会说
-
这样在DFS函数里减少了判断正方形的开销
位运算的技巧
-
用unsigned long long存储一个正方形的边的编号。
-
利用&，|运算符可以完成判断正方形是否存在，在一个状态上增加边等操作。具体实现方法是
-
#define Mark(X,K) (X=X|((Ull)1<<((K)-1))) #define Del(X,K) (X&(~((Ull)1<<((K)-1)))) #define Check(X,K) (X&(1<<((K)-1))) -
三个宏定义的作用分别是：标记数X的第K位，删除标记和检查是否有标记。
减枝
- 从预处理的正方形里，挑选最小的完整的一个，枚举删除它的边。
- 因为前面的正方形已经残缺不全了，那么不必再纠缠。同时因为从小到大的顺序，搜索树的分支会更少。
- 使用迭代加深。
附上部分代码
-
预处理正方形：下面的代码返回了以X为初始，以K为边长的正方形。并且把正方形的起始边、长度保存下来。
Ull Get (int X , int K) { Ull Ans = 0 ; int Dlt = K * ((N << 1) + 1) ; for (int i = X ; i < X + K ; ++ i) Mark (Ans , i) , Mark (Ans , Dlt + i) ; for (int i = 1 ; i <= K; ++ i) Mark (Ans , X + (2*i-1) * N + i - 1) , Mark (Ans ,X + (2*i-1) * N + i - 1 + K) ; return Ans ; } -
估价函数：利用位运算从一个状态中拆除整个正方形：
int G (Ull X) { int Ans = 0 ; for (int i = 1 ; i <= Cnt ; ++ i) { if( (S[i] & X) == S[i]) { ++ Ans ; X = X & (~S[i]) ; } } return Ans ; } -
搜索：因为前期做好了工作，搜索函数内部很简洁。
void DFS (Ull X , int Stp , int Des) { int Now = G(X) ; if (Now + Stp > Ans) return ; if (Now == 0 || Fl) { Fl = true ; return ; } while ((S[Des] & X) != S[Des]) ++ Des ; for (int i = F[Des] ; i < F[Des] + Len[Des] ; ++ i) { if (Check (X , F[Des]))DFS (Del (X , F[Des]) , Stp + 1 , Des + 1) ; if (Check (X , Len[Des] * ((N << 1) + 1) + i)) DFS (Del ( X , Len[Des] * ((N << 1) + 1) + i) , Stp + 1 , Des + 1); } for (int i = 1 ; i <= Len[Des]; ++ i) { if (Check (X , F[Des] + (2*i-1) * N + i - 1)) DFS( Del (X , F[Des] + (2*i-1) * N + i - 1) , Stp + 1 , Des + 1) ; if (Check (X , F[Des] + (2*i-1) * N + i - 1 + Len[Des])) DFS (Del (X , F[Des] + (2*i-1) * N + i - 1 + Len[Des] ), Stp + 1 , Des + 1) ; } }