defenit ctf misc-puzzle solver

solver.cc

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, vector<int> > State;
const int correct[4][4] = {
	{0, 1, 2, 3},
	{4, 5, 6, 7},
	{8, 9, 10, 11},
	{12, 13, 14, 15}
};
int puz[4][4];
int hfunc(int puz[][4]) {
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			ret += (correct[i][j] == puz[i][j] ? 1 : 0);
		}
	}
	return ret;
}
vector<pii> movable;
void dump(vector<int>& arr) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			printf("%3d ", arr[i * 4 + j]);
		}
		puts("");
	}
	puts("======================================");
}
void vec2arr(vector<int>& vec, int puz[][4]) {
	for (int i = 0; i < 16; i++) {
		int& v = vec[i];
		puz[i / 4][i % 4] = v;
	}
}
void arr2vec(int puz[][4], vector<int>& vec) {
	vec.resize(16, 0);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			vec[i * 4 + j] = puz[i][j];
		}
	}
}
void input() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			scanf("%d", &puz[i][j]);
		}
	}
}
pii findzero(int puz[][4]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (puz[i][j] == 0) return make_pair(i, j);
		}
	}
	assert(false);
	return make_pair(-1, -1);
}
bool isin(int x, int y) {
	return x >= 0 && y >= 0 && x < 4 && y < 4;
}
char dir[8][3] = {
	{-1, -2, 'q'},
	{-2, -1, 'w'},
	{-2, +1, 'e'},
	{-1, +2, 'r'},
	{+1, -2, 'a'},
	{+2, -1, 's'},
	{+2, +1, 'd'},
	{+1, +2, 'f'}
};
void unsolvable() {
	puts("unsolvable");
	exit(EXIT_SUCCESS);
}
int main() {
	input();
	State state;
	state.first = hfunc(puz);
	arr2vec(puz, state.second);
	pii zero = findzero(puz);
	int inv = 0;
	for (int i = 0; i < 16; i++) {
		for (int j = i + 1; j < 16; j++) {
			int a = state.second[i];
			int b = state.second[j];
			if (a > b) inv++;
		}
	}
	

	int id = ((zero.first + zero.second) & 1);
	if ((inv & 1) != id) {
		unsolvable();
	}
	
	map<vector<int>, State> visited;
	priority_queue<State> pq;
	visited[state.second] = make_pair(-1, vector<int>()); //initial state!
	pq.push(state);
	while (pq.size()) {
		State cur = pq.top(); pq.pop();
		if (cur.first == 16) {
			// puts("GOTCHA!");
			State p = cur;
			vector<char> move;
			while (p.second.size()) {
				if (visited[p.second].first != -1) {
					move.push_back(dir[visited[p.second].first][2]);
				}
				//To dump intermediate puzzle state
				//dump(p.second);
				p = visited[p.second];
			}
			while (move.size()) {
				putchar(move.back());
				puts("");
				move.pop_back();
			}
			return 0;
		}
		vec2arr(cur.second, puz); //puz <- 기존
		pii zero = findzero(puz);
		for (int k = 0; k < 8; k++) {
			int nx = dir[k][0] + zero.first;
			int ny = dir[k][1] + zero.second;
			if (isin(nx, ny)) {
				swap(puz[zero.first][zero.second], puz[nx][ny]); //위치 바꿈
				State next;
				next.first = hfunc(puz);
				arr2vec(puz, next.second);
				if (visited.find(next.second) == visited.end()) { //중복이 아닌 경우
					visited[next.second] = make_pair(k, cur.second); //마지막 움직임 형태와, 기존 형태를 저장함
					pq.push(next);
				}
				swap(puz[zero.first][zero.second], puz[nx][ny]); //원복 시킴
			}
		}
	}
	return 0;
}