ALDS1_13_B 8 Puzzle

Calendar Clock iconCalendar Clock icon

AOJ

Table of contents

# 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...
}

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments