算法题：uva 10318 - Security Panel

算法题：uva 10318 - Security Panel2014-03-17 csdn博客 shuangde800题目链接:

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

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

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

此外，还可以优化，把每行的状态用一个正数表示，列就用这个正数的二进制位来表示。这样判断一行是否全部亮只要O（1）就可以了.

代码：

/**uva10318 - Security Panel*暴力+减枝**/#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int MAXN= 6;int n, m;bool pat[3][3];intpath[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（"
"）;}elseputs（"Impossible."）;}return 0; }