Table of contents

• Problem
• Solution 1
• Solution 2

# Problem

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

# Solution 1

Hash table

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

# Solution 2

• Time: 32s
• Memory: 42392KB

Only diff from solution 1

// 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 < operator for map
struct Puzzle {
  ...skip...
  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;
  }
  ...skip...
};

Int bfs() {
  ...skip...
  map<Puzzle, bool> DONE; // use map instead of unordered_map
  ...skip...
}