AOJ 0131 Doctor's Strange Particles

問題文→ AIZU ONLINE JUDGE

「あるマスを選んでそこの数字を反転(1 <-> 0)させる。　この時そのマスの上下左右も反転する。　すべてを0にするために必要な反転箇所を求めよ」　という問題。

普通に考えたら O(2^100)とかで無理。　

そこで一番上の行の反転の仕方を一意に決める。するとそこから下の行も一意に決まるので O(10*10*2^10)になって間に合う。

2^nのdfsにビットを使ってみた。すごい便利ー^ ^

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<cstdlib>
#include<deque>
#include<queue>
#include<climits>
#include<cstring>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
using namespace std;
typedef vector<string> VS;
typedef vector<int> VI;
const int dx[5]={-1,0,0,0,1};
const int dy[5]={0,-1,0,1,0};
int stage[10][10];
int cnt[10][10];
int Color(int x,int y){
  int tmp=stage[x][y];
  REP(i,5){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx>=10 || ny>=10 || nx<0 || ny<0) continue;
    tmp+=cnt[nx][ny];
  }
  return tmp%2;
}
int solve(){
  for(int y=1;y<10;y++)
    for(int x=0;x<10;x++)
      if(Color(y-1,x)) cnt[y][x]=1;
  REP(i,10){ if(Color(9,i)) return -1;}
  int ret=0;
  REP(y,10) REP(x,10) ret+=cnt[y][x];
  return ret;
}
int ans[10][10];
void bit_dfs(){
  int res=-1;
  for(int i=0;i<1<<10;i++){//部分集合
    memset(cnt,0,sizeof(cnt));
    for(int j=0;j<10;j++) cnt[0][9-j]=i>>j&1;//集合切り出し
    int t=solve();
    if(t>=0 && (res<0 || res>t)){
      res=t;
      memcpy(ans,cnt,sizeof(cnt));
    }
  }
}     
int main(){
  int n; cin>>n;
  REP(i,n){
    memset(ans,0,sizeof(ans));
    memset(cnt,0,sizeof(cnt));
    memset(stage,0,sizeof(stage));
    REP(x,10) REP(y,10) cin>>stage[x][y];
    bit_dfs();
    REP(y,10){
      REP(x,10){
	cout<<ans[y][x];
	if(x<9) cout<<" ";
	else cout<<endl;
      }
    }
  }
}