ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1245 Gap

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1245


・概要
(※説明が難しいのでざっくりとした説明)
4x8の配列に1桁目が1~7、2桁目が1~4の値がランダムに入れられます。(このとき一番左の列は空ける)
その中から1桁目が1の値をすべて消し、その代わりに一番左の列の上から順に11、21、31、41といれていきます。
あとはある規則に従って値を入れ替えていき、問題文の図のような順番で並べることができる場合はその入れ替えに必要な手の最小値、できない場合は-1を出力する問題です。


・解法
幅優先探索で解くことができます。
4x8の配列をvectorで保存しておき、その最小コストをset>で保存させました。


ソースコード

#include<iostream>
#include<queue>
#include<set>
#include<vector>
#include<cstring>
using namespace std;

struct State{
   int cost;
   vector<int> layout, blank;
   
   State(){}
   State(int c, vector<int> l, vector<int> b):cost(c),layout(l),blank(b){}
};

bool check[50];
vector<int> correct, tmpLayout(32), tmpBlank;
set<vector<int> > minCost;

void display(vector<int> vec){
   for(int i = 0 ; i < 32 ; i++){
      cout << vec[i] << " " ;
      if(i%8==7)cout << endl;
   }
}

int bfs(){
   minCost.clear();
   queue<State> q;
   q.push(State(0, tmpLayout, tmpBlank));

   while(!q.empty()){
      State p = q.front();
      q.pop();
      
      if(minCost.find(p.layout)!=minCost.end())continue;
      minCost.insert(p.layout);

      bool fin = true;
      for(int i = 0 ; i < 32 ; i++){
	 if(i%8==7)continue;
	 if(correct[i]!=p.layout[i]){
	    fin = false;
	    break;
	 }
      }

      if(fin) return p.cost;

      for(int k = 0 ; k < p.blank.size() ; k++){
	 int gap = p.blank[k];
	 int key = p.layout[gap-1]+1;
	 if(key%10==8 || key==1)continue;
	 
	 for(int i = 0 ; i < 32 ; i++){
	    if(key==p.layout[i]){
	       tmpLayout = p.layout;      
	       swap(tmpLayout[gap], tmpLayout[i]);
	       tmpBlank = p.blank;
	       tmpBlank[k] = i;	       
	       break;
	    }
	 }
	 	 
	 if(minCost.find(tmpLayout)==minCost.end()){
            q.push(State(p.cost+1, tmpLayout, tmpBlank));
         }
      } 
   }
   return -1;
}

void init(){
   for(int i = 1 ; i <= 4 ; i++){
      for(int j = 1 ; j <= 8 ; j++){
	 if(j==8) correct.push_back(0);
	 else correct.push_back(10*i+j);
      }
   }
}

int main(){
   init();

   int T;
   cin >> T;
   while(T--){
      memset(check,true,sizeof(check));
      tmpBlank.clear();
      tmpLayout[0] = 11;
      tmpLayout[8] = 21;
      tmpLayout[16] = 31;
      tmpLayout[24] = 41;
      
      for(int i = 1 ; i <= 4 ; i++){
	 for(int j = 1 ; j <= 7 ; j++){
	    check[10*i+j] = false;
	 }
      }
  
      int idx = 1;
      for(int i = 0 ; i < 4*7 ; i++){
	 int v;
	 cin >> v;
	 check[v] = true;
	 if(v%10!=1)tmpLayout[idx++] = v;
	 else{
	    tmpLayout[idx] = 0;
	    tmpBlank.push_back(idx);
	    idx++;
	 }
	 if(idx%8==0)idx++;
      }
   
      bool judge = true;
      for(int i = 0 ; i < 50 ; i++)judge &= check[i];
      
      if(!judge)cout << "-1" << endl;
      else cout << bfs() << endl;
   }  
   return 0;
}