程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVa1603 - Square Destroyer

UVa1603 - Square Destroyer

編輯:C++入門知識

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<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved