目次

• 問題
• 解説
• 解答

# 問題

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

8パズルを16マスに拡張したバージョン.
必要な探索量が膨大になるので時間とメモリにさらなる工夫が必要.

# 解説

基本的には8パズルのアルゴリズムを使用し、変更するのは以下の1点.

8パズルでは次の可能性の盤面を適当な順番でキューから取り出していたのに対し、今回は盤面に何らかの点数を付与してそれが良い順にキューを処理する.
点数として、その盤面に到達するまでにかかった遷移回数＋正解盤面までのマンハッタン距離の総和を使用する.

まず、遷移回数はキューに新しい盤面を入れるごとに＋１する.
正解盤面までの距離が同じ場合は遷移回数が少ないほうが優秀な解答なので遷移回数を少ない方から処理する.

マンハッタン距離というのは、座標上の点間のxの距離とyの距離の合計.
16マスあるので、それぞれの点の正解までのマンハッタン距離を合計すればざっくりとした必要遷移回数が求められる.

これらの合計が少ないほうが優秀な解答なので優先度付きキューを使って優先的に探索を進めていく.

盤面を表すのにvectorや遷移を表すのにstringを使うと時間制限超過でミスになるので使わない.

# 解答

• 時間: 1:51s
• メモリ: 257108KB

// 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 4
#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'};
Int MDT[NN][NN];


class Puzzle {
public:
  Int vec[NN];
  Int blank, estimate, cost;
  
  Puzzle(): blank(-1), estimate(-1), cost(0) {
    loop(n,0,NN) vec[n] = -1;
  }
  
  Puzzle(Int vec[NN], Int blank, Int cost) {
    loop(n,0,NN) this->vec[n] = vec[n];
    this->blank = blank;
    this->cost = cost;
    
    updateEstimate();
  }
  
  bool operator < (const Puzzle &other) const {
    return estimate > other.estimate;
  }
  
  bool operator == (const Puzzle &other) const { 
    loop(n,0,NN) {
      if (vec[n] != other.vec[n]) return false;
    }
    
    return true;
  }
  
  void updateEstimate() {
    estimate = cost;
    loop(n,0,NN) {
      if (vec[n] == NN) continue; // blank
      estimate += MDT[n][vec[n]-1];
    }
  }
  
  Puzzle move(Int dir) {
    Int sx, sy, tx, ty;
    sx = blank % N;
    sy = blank / N;
    
    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.cost++;
    p.updateEstimate();
    return p;
  }
};

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


Int targetVec[NN] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
Puzzle target(targetVec, 15, -1);
Puzzle source;


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

void input() {
  Int vec[NN];
  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;
        vec[h*N+w] = NN;
      }
    }
  }
  loop(n,0,NN) source.vec[n] = vec[n];
  source.blank = blank;
  source.cost = 0;
  source.updateEstimate();
}

void solve() {
  loop(i,0,NN) {
    loop(j,0,NN) {
      MDT[i][j] = abs(i/N - j/N) + abs(i%N - j%N);
    }
  }
  cout << bfs() << endl;
}


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