AOJ

# # Problem

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

# # Solution 1

Hash table

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

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

// 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!