uva 10318 - Security Panel

タイトルリンク:
まず、0より大きい偶数を選択すると、効果がないのと同じであるため、各格子は1回しか選択できないと判断できます.
そして、r*cのマトリクスからいくつかの格子を選択して「点灯」操作を行い、最終的にすべての格子が「明るい」状態になるように理解することができる.では,各格子に点灯操作があるか,ないかのいずれかで,合計複雑度は2^25であり,明らかに減枝が必要である.
1行目の1列目から左から右へ、上から順に選択すると、現在位置(x,y)については、x-2以前の行数に影響を与えることができなくなるので、x行目になると、x-2行目が全て点灯していない場合には減枝する.
また,各行の状態を正数で表し,列をこの正数のバイナリビットで表す最適化も可能である.このように1行が全て明るいか否かを判断するのはO(1)でよい.
コード:

/*
 *  uva  10318 - Security Panel
 *    +  
 *
 */
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int MAXN= 6;
int n, m;
bool pat[3][3];
int  path[MAXN*MAXN], mat[MAXN], minx;

inline void read(){
    memset(mat,0, sizeof(mat));
    for(int i=0; i<3; ++i){
        for(int j=0; j<3; ++j)
            pat[i][j] = getchar()=='*'?true:false;
        getchar();
    }
}

inline bool checkRow(int r){
    if(mat[r] != (1<<m)-1) return false;
    return true;

}
inline bool checkAll(){ 
    //           （     1)
    if(n>1 && checkRow(n-1) && checkRow(n-2) ||
       n==1 && checkRow(0)) 
        return true;
    return false;

}
inline void cover(int r,int c){
    for(int i=r-1; i<=r+1; ++i){
        if(i<0 || i>=n) continue;
        for(int j=c-1; j<=c+1; ++j){
            if(j<0 || j>=m) continue;
            if(pat[i-r+1][j-c+1]) 
                mat[i] ^= (1<<j);
        }
    }

}

bool dfs(int cur, int pathNum){

    int r=cur/m, c=cur-r*m;
    if(r-2>=0 && !checkRow(r-2))
        return false ;
    if(r>=n-2 || cur==n*m){
        if(checkAll()){
            minx = pathNum;
            return true;
        }
        if(cur==n*m) return false;

    }
	if(dfs(cur+1, pathNum)) return true;
	cover(r, c);
	path[pathNum] = cur+1;
	if(dfs(cur+1, pathNum+1)) return true;
	cover(r, c);
    return false;
}

int main(){

    int cas=1;
    while(~scanf("%d%d%*c",&n,&m) && n+m) {


        read(); 
        printf("Case #%d
", cas++);
        if(dfs(0, 0)){
            printf("%d", path[0]);
            for(int i=1; i<minx; ++i)
                printf(" %d", path[i]);
            putchar('
');

        }else
            puts("Impossible.");

    }

    return 0;   
}