首页 > 代码库 > POJ1222_EXTENDED LIGHTS OUT
POJ1222_EXTENDED LIGHTS OUT
给出5*6的位置，每个位置有一个灯，一开始每个灯有各自的状态，你可以选定一些位置使得所有与这个位置相邻以及位置本身的灯都取反。
输出合法方案。
本来是找高斯消元找到这个题目的，可是。。。。我发现可以直接状态压缩dfs，于是就水过了，高斯消元还是不会。怒坑。
枚举是这样的，当前6位数表示这一行每个灯的状态，由于当前这一排灯仅受相邻两排的影响，当我搜索到下一排的时候，判断对于当前这一排是否是一个合法的方案，及时剪枝。
一直扫下去就是答案了。
召唤代码君：
#include <iostream>#include <cstring>#include <cstdio>using namespace std;int a[7][8],ans[7];int T,n,m,cas=0,c[8];int f[8];bool findans;bool check(int cur){ int tmp=ans[cur]; for (int i=1; i<=6; i++) f[i]=tmp&1,tmp>>=1; for (int i=1; i<=6; i++){ tmp=(ans[cur-1]&c[i])==(ans[cur+1]&c[i])?1:0; tmp^=a[cur][i]^f[i-1]^f[i]^f[i+1]; if (!tmp) return false; } return true;}void dfs(int cur){ if (cur==5){ if (check(cur)) findans=true; return; } for (int i=0; i<c[7]; i++){ ans[cur+1]=i; if (cur>0 && !check(cur)) continue; dfs(cur+1); if (findans) return; }}int main(){ c[1]=1; for (int i=2; i<=7; i++) c[i]=c[i-1]+c[i-1]; scanf("%d",&T); while (T--) { findans=false; for (int i=1; i<=5; i++) for (int j=1; j<=6; j++) scanf("%d",&a[i][j]); dfs(0); printf("PUZZLE #%d\n",++cas); for (int i=1; i<=5; i++){ printf("%d",ans[i]&1); for (int j=2; j<=6; j++) printf(" %d",(ans[i]&c[j])?1:0); printf("\n"); } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。