PKU 2965-The Pilots Brothers' refrigerator
問題概要
4x4のスイッチがある.全てのスイッチをOFFにしろ。ただしあるスイッチをクリックするとその列とその行のスイッチ全てが反転される。
解法
単純に全探索だと間に合わないので半分全列挙する。
実装(C++)
#include <iostream> #include <algorithm> using namespace std; string s[4]; int MAP[4][4]; void put(int x,int y){ MAP[x][y]=!MAP[x][y]; for(int i=0;i<4;i++){ MAP[x][i]=!MAP[x][i]; MAP[i][y]=!MAP[i][y]; } } bool is_exit(){ for(int i=0;i<4;i++)for(int j=0;j<4;j++){ if(MAP[i][j])return false; } return true; } void show(){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ cout<<MAP[i][j]; } cout<<endl; } } int encode(){ int res=0; for(int j=0;j<16;j++){ if(MAP[j%4][j/4])res|=1<<j; } return res; } int mincost[1<<16]; int main() { fill(mincost,mincost+(1<<16),(1<<17)-1); for(int i=0;i<4;i++)cin>>s[i]; for(int i=0;i<4;i++)for(int j=0;j<4;j++){ MAP[i][j]=(s[i][j]=='+'); } int ans=(1<<16)-1; for(int i=0;i<1<<8;i++){ for(int j=0;j<8;j++){ if((i>>j)&1){ put(j/4,j%4); } } int e=encode(); if(__builtin_popcount(mincost[e])>__builtin_popcount(i)){ mincost[e]=i; } for(int j=0;j<8;j++){ if((i>>j)&1){ put(j/4,j%4); } } } for(int i=0;i<4;i++)for(int j=0;j<4;j++){ MAP[i][j]=0; } for(int i=0;i<1<<8;i++){ for(int j=0;j<8;j++){ if((i>>j)&1){ put(j/4+2,j%4); } } int e=(encode())&65535; if(__builtin_popcount(ans)>__builtin_popcount(mincost[e])+__builtin_popcount(i)){ ans=(i<<8)+mincost[e]; } for(int j=0;j<8;j++){ if((i>>j)&1){ put(j/4+2,j%4); } } } cout<<__builtin_popcount(ans)<<endl; for(int j=0;j<16;j++){ if((ans>>j)&1){ cout<<j/4+1<<" "<<j%4+1<<endl; } } return 0; }