PKU 3221-Diamond Puzzle

問題概要

問題文にある図のようなスライドパズル（0の部分が空）を解け。

解法

パターンは7!(=5040)しかないので最初にBFSして全ての解を求める

実装(C++)

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

int d[7][7]={
  {2,4,6,-1},
  {2,6,-1},
  {1,3,0,-1},
  {2,4,-1},
  {0,3,5,-1},
  {4,6,-1},
  {0,1,5,-1}
};

map<string,int> ans;

void bfs(){
  string start="0123456";
  ans[start]=0;
  queue<string> que;
  que.push(start);
  while(!que.empty()){
    string now=que.front();que.pop();
    int cost=ans[now];
    for(int i=0;i<7;i++){
      if(now[i]!='0')continue;
      for(int j=0;d[i][j]>=0;j++){
        swap(now[i],now[d[i][j]]);
        if(ans.count(now)==0||(ans[now]>cost+1)){
          ans[now]=cost+1;
          que.push(now);
        }
        swap(now[i],now[d[i][j]]);
      }
    }
  }
}
int main(){
  bfs();
  int n;
  cin>>n;
  string s;
  for(int i=0;i<n;i++){
    cin>>s;
    if(ans.count(s)==0){
      cout<<-1<<endl;
    }else{
     cout<<ans[s]<<endl;
    }
  }
}