AOJ 1245 - Gap

問題概要

縦4×横8にカード(または何もない)が並べられている。カードに書かれている数字は11~17,21~27,31~37,41~47(カードの合計枚数は28枚)である。最初、各行の1列目にはカードが置かれていない。まず、(縦,横) = (1,1),(2,1),(3,1),(4,1)にそれぞれ11,21,31,41のカードを置く。すると最初に11,21,31,41が置かれていた場所にはカードが置かれていない状態になる。このカードが置かれていないマスの左隣のカードに着目して、そのカードの1の位が7でなければ、その右隣のカードが置かれていないマスに「左隣のカードの数字+1」の数字のカードを持ってくることができる。そして持ってきたカードが元々あった場所にはカードが置かれていない状態になる。この操作を繰り返して以下の状態にするためには最小回数でいけるか。もし以下の状態にできない場合は-1を出力する。

• ゴールの状態

解法

現在のカードの情報を状態に持ち、bfsをする。
既に訪れた状態をvisitedとしてメモする。

計算量が微妙だが、通る。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
typedef vector<int> Vec;
typedef pair<Vec,int> P;
 
bool check(Vec &v){
  for(int i = 0 ; i < 32 ; i++){
    if((i+1) % 8 == 0) continue;
    if((i/8+1)*10+i%8+1 != v[i]) return false;
  }
  return true;
}
 
int bfs(Vec &start,Vec &space){
  queue<P> Q;
  queue<Vec> S;
  Q.push(P(start,0));
  S.push(space);
  set<Vec> visited;
  visited.insert(start);
 
  while(!Q.empty()){
    P p = Q.front(); Q.pop();
    Vec s = S.front(); S.pop();
    if(check(p.first)) return p.second;
     
    for(int i = 0 ; i < 4 ; i++){
      if(p.first[s[i]-1] % 10 == 7) continue;
      for(int j = 0 ; j < 32 ; j++){
        if(p.first[s[i]-1]+1 == p.first[j]){
          swap(p.first[s[i]],p.first[j]);
          int tmp = s[i]; s[i] = j;
          if(!visited.count(p.first)){
            visited.insert(p.first);
            Q.push(P(p.first,p.second+1));
            S.push(s);
          }
          s[i] = tmp;
          swap(p.first[s[i]],p.first[j]);
        }
      }
    }
  }
  return -1;
}
 
int main(){
  int Tc;
  cin >> Tc;
  while(Tc--){
    Vec v(32),space;
    for(int i = 0 ; i < 32 ; i++){
      if(i % 8 != 0){
        cin >> v[i];
        if(v[i]%10 == 1){
          v[i] = 0;
          space.push_back(i);
        }
      }else{
        v[i] = (i/8+1)*10+1;
      }
    }
    cout << bfs(v,space) << endl;
  }
  return 0;
}