AOJ

# # Problem

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

# # Solution

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

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();
}


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!