AOJ 1110 Patience

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1110
図のような形で数字が並べられている。
このとき、隣接する8方向に同じ数字があれば、そのペアを消去できる。
可能なかぎり消去していったときに、消しきれないカードの枚数の最小値を求めろというような問題。

2週間ぶりぐらいなAOJ。
面白そうという気持ちとnext関数の作成が若干面倒くさいというような気持ちの間で放置していた問題でした。
幅優先探索。

int get(ll in,int x,int y){
  int pos=x*4+y;
  return (in>>pos*3)&7;
}

ll next(ll in,int p,int q){
  in=(in&((1LL<<q*3)-1))|((in&~((1LL<<(q+1)*3)-1))>>3);
  in=(in&((1LL<<p*3)-1))|((in&~((1LL<<(p+1)*3)-1))>>3);
  return in;
}

int tx[]={1,1,1,0},ty[]={-1,0,1,1};


main(){
  int n;
  cin>>n;
  while(n--){
    ll st=0;
    rep(i,20){
      ll x;
      cin>>x;
      st|=x<<i*3LL;
    }
    queue<pair<int,ll> > q;
    q.push(mp(0,st));
    set<ll> app;
    int ans=0;
    while(!q.empty()){
      int cc=q.front().F;
      ll cst=q.front().S;
      q.pop();
      if(app.count(cst))continue;
      app.insert(cst);
      ans=cc;
      rep(i,20){
        if(((cst>>i*3)&7)==0)break;
        int cx=i/4,cy=i%4;
        rep(j,4){
          int nx=cx+tx[j],ny=cy+ty[j];
          if(nx<0 || 5<=nx || ny<0 || 4<=ny)continue;
          if(get(cst,nx,ny)==get(cst,cx,cy)){
            ll nst=next(cst,cx*4+cy,nx*4+ny);
            if(app.count(nst))continue;
            q.push(mp(cc+1,nst));
          }
        }
      }
    }
    cout<<20-2*ans<<endl;
  }
}