AOJ1245.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef vector<int> Array;
typedef vector<Array> Mat;

bool isGoal(Mat t) {
  REP(i,4) REP(j,7)
    if (t[i][j] != i * 10 + j + 11) return false;
  return true;
}

int bfs(const Mat& dat) {
  queue<pair<int,Mat>> que;
  que.push({0, dat});
  set<Mat> visited;
  while (!que.empty()) {
    int s = que.front().first;
    Mat t = que.front().second;
    que.pop();
    if (visited.find(t) != visited.end()) continue;
    visited.insert(t);
    if (isGoal(t)) return s;
    REP(i,4) REP(j,7) if(t[i][j+1] == 0) {
      Mat tt = t;
      REP(ii,4) REP(jj,8) if (tt[ii][jj] == tt[i][j] + 1)
        swap(tt[i][j+1], tt[ii][jj]);
      que.push({s+1, tt});
    }
  }
  return -1;
}

int main() {
  int n;
  cin >> n;
  while (n--) {
    Mat t(4, Array(8));
    REP(i,4) for (int j = 1; j < 8; j++) cin >> t[i][j];
    REP(i,4) REP(j,8) if (t[i][j] % 10 == 1) t[i][j] = 0;
    REP(i,4) t[i][0] = i * 10 + 11;
    cout << bfs(t) << endl;
  }
  return 0;
}