Pの競プロ記

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

AOJ 1268 Cubic Eight-Puzzle

概要


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

図3(問題文を見てください)のようなサイコロが8つあり、それが図4のように並べられています。
サイコロを転がして入力で与えられるような目的の形にするまでの最短コストを求める問題です。(コストが30を超える場合は-1を出力)


解法


反復深化深さ優先探索で求めることができます。

サイコロの状態を全て持たせて幅優先探索すると、状態数がとても多いためMLEになってしまいます。 そこで用いるのが反復深化深さ優先探索です。(私は最近この探索方法を知りました。)

また探索する時には目的の形と現在の形を比較して枝刈りを行います。


ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
 
static const int dx[]={0,1,0,-1};
static const int dy[]={1,0,-1,0};
 
/*
  B: Blue
  W: White
  R: Red
  E: Empty
*/
 
struct Dice{
  //top, front, right, left, back, bottom;
  char side[6];
  Dice(){}
  Dice(char sd[]){
    rep(i,6) side[i] = sd[i];
  }
 
  void rotate(int op){
    char tmp = ' ';
    //右に倒す
    if(op==0){
      tmp = side[0];
      side[0] = side[3];
      side[3] = side[5];
      side[5] = side[2];
      side[2] = tmp;
    }
 
    //前に倒す
    if(op==1){
      tmp = side[0];
      side[0] = side[4];
      side[4] = side[5];
      side[5] = side[1];
      side[1] = tmp;
    }
       
    //左に倒す
    if(op==2){
      tmp = side[0];
      side[0] = side[2];
      side[2] = side[5];
      side[5] = side[3];
      side[3] = tmp;
    }
       
    //後ろに倒す
    if(op==3){
      tmp = side[0];
      side[0] = side[1];
      side[1] = side[5];
      side[5] = side[4];
      side[4] = tmp;
    }
  }
};
 
int sx,sy;
char goal[3][3];
Dice initDice;
Dice emptyDice;
Dice G[3][3];
 
void makeDice(){
  char side[6];
   
  rep(i,6) side[i] = 'E';
  emptyDice = Dice(side);
   
  side[0] = side[5] = 'W';
  side[1] = side[4] = 'R';
  side[2] = side[3] = 'B';
  initDice = Dice(side);
}
 
void init(){
  rep(i,3) rep(j,3) G[i][j] = initDice;
  G[sx][sy] = emptyDice;
}
 
int check(){
  int diff = 0;
  bool emptyFlag = false;
  rep(i,3){
    rep(j,3){
      if(goal[i][j] != G[i][j].side[0]) diff++;
      if(goal[i][j]=='E' && G[i][j].side[0]=='E') emptyFlag = true;
    }
  }
  if(!emptyFlag) diff--;
  return diff;
}
 
bool dfs(int ex, int ey, int depth, int limit, int dir){
  int diff = check();
  if(diff==0) return true;
  if(diff + depth > limit) return false;
   
  rep(k,4){
    int px = ex + dx[k];
    int py = ey + dy[k];
    if(0<=px&&px<3 && 0<=py&&py<3){
      int op = (k + 2) % 4;
      if(op==dir) continue;
      Dice tmp = G[px][py];
      G[px][py].rotate(op);
      swap(G[ex][ey], G[px][py]);
            
      if(dfs(px, py, depth+1, limit, k)) return true;
     
      swap(G[ex][ey], G[px][py]);
      G[px][py] = tmp;
    }
  }    
   
  return false;
}
 
int main(){
  makeDice();
  while(cin >> sy >> sx && (sx|sy)){
    sx--; sy--;
    rep(i,3) rep(j,3) cin >> goal[i][j];
    int ans = -1;
    rep(i,31){
      init();
      if(dfs(sx, sy, 0, i, -1)){
        ans = i;
        break;
      }
    }
    cout << ans << endl;
  }
  return 0;
}