PKU 1753 Flip Game

http://poj.org/problem?id=1753
ライツアウト

以前の似たような問題では上の列を全通り試しましたが、今回はマスの数が少ないのと、全部白か黒の場合を求めるのは場合分けが面倒くさくなりそうだったの幅優先探索で解いてみました。

bool vis[1<<16];


int next(int in,int x,int y){
  in^=(1<<(x*4+y));
  rep(i,4){
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<0 || 4<=nx ||
       ny<0 || 4<=ny)continue;
    in^=(1<<(nx*4+ny));
  }
  return in;
}

main(){
  int s=0;
  rep(i,4){
    string in;
    cin>>in;
    rep(j,4){
      if(in[j]=='b')s|=1<<i*4+j;
    }
  }
  queue<PI> q;
  q.push(mp(0,s));
  while(!q.empty()){
    int cc=q.front().F,st=q.front().S;
    q.pop();
    if(st==0 || st==(1<<16)-1){
      cout<<cc<<endl;
      return 0;
    }
    if(vis[st])continue;
    vis[st]=true;
    rep(i,16){
      int x=i/4,y=i%4;
      int ne=next(st,x,y);
      if(vis[ne])continue;
      q.push(mp(cc+1,ne));
    }
  }
  cout<<"Impossible"<<endl;
}