日々精進

aikoと旅行とプログラミング

【AOJ ALDS1_13】B: Heuristic Search - 8 Puzzle

問題

| アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • DFSをして正しい並びになったかを判定し, その時のターン数を返す.
  • 探索した盤面はフラグを立てておき, 同じ状態を2回以上探索しないようにする.
    • mapって比較の"<“が定義されてないと使えないのを初めて知った.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct Puzzle{
  int field[9];
  int space;
  int turn;

  bool operator < (const Puzzle& a) const{
    rep(i, 9){
      if(a.field[i] == field[i]) continue;
      return field[i] >  a.field[i];
    }
    return false;
  }
};

bool check(Puzzle p){
  rep(i, 9){
    if(p.field[i] != i+1) return false;
  }
  return true;
}

int solve(Puzzle in){
  queue<Puzzle> q;  
  map<Puzzle, bool> mp;

  q.push(in);
  mp[in] = true;
  
  // bfs
  while(!q.empty()){
    Puzzle p = q.front(); q.pop();
    if(check(p)) return p.turn;
    int x = p.space % 3;
    int y = p.space / 3;
    rep(i, 4){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || 2 < nx || ny < 0 || 2 < ny) continue;
      Puzzle tmp = p;
      swap(tmp.field[p.space], tmp.field[3 * ny + nx]);
      tmp.space = 3 * ny + nx;
      if(mp[tmp] == false){
    mp[tmp] = true;
    tmp.turn++;
    q.push(tmp);
      }
    }
  }
  return -1;
}

signed main(){
  Puzzle in;
  
  rep(i, 9){
    cin >> in.field[i];
    if(in.field[i] == 0){
      in.field[i] = 9;
      in.space = i;
    }    
  }

  in.turn = 0;
  cout << solve(in) << endl;
}