# 問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_B

# 解説

パズルの盤面を状態とみなして、可能な状態遷移を繰り返して目標とする盤面となるまでの最短遷移回数が問題の答え.
最短距離を求める問題なので、幅優先探索で状態変化をたどる.
最初に見つかった答えがそのまま最短距離となる.
すでに調べた盤面はハッシュテーブルなどで管理し無駄な計算を省く.

# 解答1

ハッシュテーブルバージョン

この問題の場合Puzzle構造体のハッシュのために $O(N)$ 、ハッシュを使ってのアクセスは $O(1)$ なので、Puzzle構造体をキーとしたアクセスは $O(N)$ .
マップ（二分探索木）の場合はソートされるので、全要素の比較に $O(N)$ 、アクセスに $O(\log N)$ なので、 $O(N\times\log N)$ .ハッシュテーブルが有利。

(※ $N = 8$ )

時間: 20s
メモリ: 41252KB

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define N 3
#define NN (N*N)

vector<Int> dx = {0, 0, -1, 1};
vector<Int> dy = {-1, 1, 0, 0};
vector<char> dirs = {'u', 'd', 'l', 'r'};


struct Puzzle {
  vector<Int> vec;
  Int blank;
  string path;
  
  Puzzle(): vec(NN, -1), blank(-1), path("") {
  }
  
  Puzzle(vector<Int> &vec, Int blank, string path) {
    this->vec = vec;
    this->blank = blank;
    this->path = path;
  }
  
  bool operator == (const Puzzle &other) const { 
    loop(n,0,NN) {
      if (vec[n] != other.vec[n]) return false;
    }
    
    return true;
  }
  
  Puzzle move(Int dir) {
    // i = h * N + w
    Int sx = blank % N;
    Int sy = blank / N;
    Int tx, ty;
    
    switch (dir) {
      case 0: 
      case 1:
      case 2:
      case 3:
        tx = sx + dx[dir];
        ty = sy + dy[dir];
        break;
      default:
        cout << "Invalid dir: " << dir << endl;
        exit(1);
        break;
    }
    
    Puzzle p;
    if (tx < 0 || N <= tx || ty < 0 || N <= ty) {
      return p;
    }
    
    p = *this;
    swap(p.vec[sy * N + sx], p.vec[ty * N + tx]);
    p.blank = ty * N + tx;
    p.path += dirs[dir];
    return p;
  }
  
  void dump() {
    loop(n,0,NN) cout << vec[n] << ' '; cout << endl;
  }
  
  void dump2() {
    loop(h,0,N) {
      loop(w,0,N) {
        cout << vec[h * N + w] << ' ';
      }
      cout << endl;
    }
  }
};

namespace std {

  template <>
  struct hash<Puzzle>
  {
    std::size_t operator()(const Puzzle& p) const
    {
      std::size_t seed = p.vec.size();
      for(auto& i : p.vec) {
        seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
      }
      return seed;
    }
  };
}


vector<Int> targetVec = {1, 2, 3, 4, 5, 6, 7, 8, 0};
Puzzle target(targetVec, 8, "");
Puzzle source;


Int bfs() {
  queue<Puzzle> Q;
  unordered_map<Puzzle, bool> DONE;
  
  Q.push(source);
  DONE[source] = true;
  
  while (!Q.empty()) {
    Puzzle top = Q.front(); Q.pop();
    if (top == target) return top.path.length();
    
    loop(dir,0,dirs.size()) {
      Puzzle p = top.move(dir);
      if (p.blank== -1) continue; // Invalid board
      if (DONE[p]) continue;
      Q.push(p);
      DONE[p] = true;
    }
  }
  
  cout << "No solution" << endl;
  return -1;
}

void input() {
  vector<Int> vec(NN, -1);
  Int blank = -1;
  loop(h,0,N) {
    loop(w,0,N) {
      cin >> vec[h*N + w];
      if (vec[h*N + w] == 0) blank = h * N + w;
    }
  }
  source.vec = vec;
  source.blank = blank;
}

void solve() {
  cout << bfs() << endl;
}


int main() {
  input();
  solve();
}

# 解答2

マップ（二分探索木バージョン）

時間: 32s
メモリ: 42392KB

（差分のみ掲載）

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

// mapのためにPuzzle構造体に<を定義
struct Puzzle {
  ...省略...
  bool operator < (const Puzzle &other) const {
    loop(n,0,NN) {
      if (vec[n] == other.vec[n]) continue;
      return vec[n] > other.vec[n];
    }
    
    return false;
  }
  ...省略...
};

Int bfs() {
  ...省略...
  map<Puzzle, bool> DONE; // unordered_mapの代わりにmapを使用
  ...省略...
}

ALDS1_13_B 8パズル

# 問題

# 解説

# 解答1

# 解答2

コメント