PKU 2965 The Pilots Brothers' refrigerator

http://poj.org/problem?id=2965
4x4のハンドルがついている冷蔵庫があって、全てのハンドルを開けたい。
一回の操作で、位置(i,j)を指定すると、列i、行jの全てのハンドルが反転する。
このとき全てのカギを開けるのに必要な最小の操作回数を求めろというような問題。
ただし、'+'は閉まっていることを、'-'は開いていることを表す。

最初愚直に幅優先と、経路記憶をやろうとしてTLEでした。
よく考えると変形ライツアウトな感じだったので、どのマスを指定するかを全探索しました。

int next(int st,int x,int y){
  rep(i,4)st^=1<<4*i+x;
  rep(i,4)st^=1<<y*4+i;
  st^=1<<4*y+x;
  return st;
}


char in[5];

main(){
  int st=0;
  rep(i,4){
    gets(in);
    rep(j,4)if(in[j]=='+')st|=1<<i*4+j;
  }


  int ans=0;
  int co=16;
  rep(i,1<<16){
    if(ans && __builtin_popcount(i)>=co)continue;
    int cst=st;
    rep(j,16){
      if((i>>j)&1)cst=next(cst,j/4,j%4);
    }
    if(cst==0){
      ans=i;
      co=__builtin_popcount(i);
    }
  }
  printf("%d\n",co);
  rep(i,16){
    if(ans>>i&1)printf("%d %d\n",i%4+1,i/4+1);
  }
}