算法题：uva 10318

题目链接:

首先，可以确定每个格子只能选一次，因为选任何大于0的偶数次，等于没有效果 一样。

然后，就可以把这题理解成从r*c的矩阵中选择一些格子进行“点亮”操作，使得最终所 有格子都是“亮”的状态。那么，每个格子要么有点亮操作，要么没有，总共复杂度为2^25，显然必须 进行减枝。

假设从第一行第一列开始，从左往右，从上往下一次依次选择，对于当前所在位置（ x, y），它已经不能影响到x-2以前的行数了，所以当到x行时，如果第x-2行没有全部点亮，则进行减枝 。

此外，还可以优化，把每行的状态用一个正数表示，列就用这个正数的二进制位来表示。 这 样判断一行是否全部亮只要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\n", cas++);
        if(dfs(0, 0)){
            printf("%d", path[0]);
            for(int i=1; i<minx; ++i)
                printf(" %d", path[i]);
            putchar('\n');  

        }else
            puts("Impossible.");  

    }  

    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， 点亮
， mat
， 状态
， pat acm题
， 算法题
， 一行
， 从左往右
， javascript算法题
格子
jb10318、gb10318、jb/t 10318、，以便于您获取更多的相关知识。