Table of contents

• Problem
• Solution

# Problem

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

# Solution

• Time: 1:51s
• Memory: 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();
}