UVa1603 - Square Destroyer

UVa1603 - Square Destroyer

題意：

給定一個火柴棒拼成的方格陣，然後去掉一些火柴棒，問至少再去掉幾根火柴棒能夠讓圖中一個正方形都沒有。

思路：

1. 由於題目中給定了 n 的范圍，2 * n * (n + 1) <= 60 -> 所以能夠保證所有的火柴用 __int64 的位運算表示;

2. 問題的關鍵在於如何生成火柴構成的方陣，以及生成方陣之後如何去搜索;

3. 啟發式函數 h 的計算需要考量：如果刪除了某個方陣的一個邊，則能夠保證 h(s1) <= h(s2) + C(s1, s2)，其中 C(s1, s2) = 1，h(s1) - h(s2) <= 1，可以用反證法證明;

4. 各種位運算的范圍要明確，如 1<

紫書分析：迭代加深搜索為主算法框架，搜索對象有兩種，

1.每次考慮一個沒有被破壞的正方形，在邊界上找一根火柴拿掉，搜索對象是正方形，應先考慮小正方形，在考大打正方形，因為小正方形被破壞之後，大正方形就被破壞了，但是反過來卻不一定，還可以加入最優性減枝，即把每個正方形看成一個頂點，有公共火柴的正方形連城一條邊，則每個連通分量至少拿走一根火柴。

2.每次找一個至少能破壞一個正方形的火柴，然後拿掉。搜索對象是火柴，應該搜索盡量能破壞最多正方形的火柴，這需要計算出考慮每根火柴可以破壞掉多少個正方形，從小到大排序d[1],...當d[1]為1時即可停止搜索，因為此時可以直接計算出還需要的火柴個數，這個d數組也可以用於最優性減枝，找到最小的i，使得d[1]+d[2]=...+d[i]<=k（其中k為還省得正方形個數），至少還要i跟火柴。

還能用DLX算法解決。

#include
#include
#include
#include
using namespace std;
const int INFS = 0x7fffffff;
int N,C,E,bound;
__int64 square[100], base[6][6];
bool succ;

inline int __int64 getflag(int i){
    return ((__int64)1<<(i-1));
}
inline int geth(int i,int j){
    return (2*N+1)*(i-1)+j;
}
inline int getv(int i,int j){
    return (2*N+1)*(i-1)+j+N;
}
void build()
{
    C=0;
    memset(base,0,sizeof(base));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            base[i][j] |= getflag(geth(i,j)) | getflag(geth(i+1,j));
            base[i][j] |= getflag(getv(i,j)) | getflag(getv(i,j+1));
            square[C++] = base[i][j];
        }
    }
    for(int size=2;size<=N;size++){
        for(int i=1;i+size-1 <= N;i++){
            for(int j=1;j+size-1<=N;j++){
                square[C]=0;
                for(int a=0;abound){
        return depth+h;
    }
    int newbound = INFS;
    for(int i=1;i<=E;i++){
        if(u & getflag(i)){
            int b=dfs(state ^ getflag(i),depth+1);
            if(succ)
                return b;
            newbound = min(b,newbound);
        }
    }
    return newbound;
}
int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--){
        scanf("%d",&N);
        build();

        E = 2*N*(N+1);
        int k;
        __int64 state = ((__int64)1<