AOJ : 1245 - Gap

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1245

日本語訳をしてくださっていた方がいたので, そちらを参考にさせていただきました.
ありがとうございます.
http://bal4u.dip.jp/mt/program/2004/10/gap.html

アルゴリズム

幅優先探索で解けます.
素直に, 各状態から4分岐していって, 同じ盤面になったら枝刈りという方法で通せました.

プログラム

class P{
public:
  int cost;
  vector<int> v,pos,gap;

  P(){}
  P(int _cost,vector<int> _v,vector<int> _pos,vector<int> _gap){
    cost = _cost;
    v = _v;
    pos = _pos;
    gap = _gap;
  }

  bool goal(){
  }
};

bool goal(vector<int> &v){
  rep(i,4){
    rep(j,7){
      int idx = i * 8 + j;
      if(v[idx] / 10 != i + 1 || v[idx] % 10 != j + 1) return false;
    }
  }
  return true;
}

int bfs(P start){
  queue<P> open;
  set<vector<int> > closed;
  open.push(start);
  closed.insert(start.v);

  while(!open.empty()){
    P p = open.front(); open.pop();

    rep(i,4){
      vector<int> nv = p.v;
      vector<int> npos = p.pos;
      vector<int> ngap = p.gap;
      int idx = ngap[i];
      int val = nv[idx-1] + 1;
      if(npos[val] == 0) continue;

      nv[idx] = val;
      nv[npos[val]] = 0;
      ngap[i] = npos[val];
      npos[val] = idx;

      if(closed.find(nv) != closed.end()) continue;
      closed.insert(nv);

      if(goal(nv)){
        return p.cost+1;
      }
      open.push(P(p.cost+1,nv,npos,ngap));
    }
  }

  return -1;
}

int main(void){
  int T;
  scanf("%d",&T);

  while(T--){
    vector<int> v(32);
    vector<int> pos(50);
    vector<int> gap;

    rep(i,4){
      rep(j,7){
        int idx = i * 8 + j + 1;
        scanf("%d",&v[idx]);
        if(v[idx] % 10 == 1){
          int row = v[idx] / 10 - 1;
          v[row*8] = v[idx];
          v[idx] = 0;
          gap.push_back(idx);
        }
        else{
          pos[v[idx]] = idx;
        }
      }
    }

    printf("%d\n",goal(v) ? 0 : bfs(P(0,v,pos,gap)));
  }
}