FunOfSearching-9-4.cpp

#include <iostream>
#include <cmath>
using namespace std;

int cnts = 0;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int t[4][4];
int dst[4][4][16];
bool flag = false;

void init() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) t[i][j] = 4 * (i * 4 + j);
	}

	// dst[i][j][k] : マス (i, j) と、最終的にピース k があるべき場所、の間の距離
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 1; k < 16; k++) {
				int sx = (((k + 15) % 16) / 4), sy = (((k + 15) % 16) % 4);
				dst[i][j][k] = abs(i - sx) + abs(j - sy);
			}
		}
	}
}

bool dfs(int dep, unsigned long long V, int px, int py, int prevdir, int exp) {
	if (flag == true) return true;
	if (dep == 0) {
		flag = true;
		return true;
	}

	for (int i = 0; i < 4; i++) {
		int sx = px + dx[i], sy = py + dy[i];
		if (sx < 0 || sy < 0 || sx > 3 || sy > 3) continue;
		if (((i + 2) & 3) == prevdir) continue;

		// V1, V2 はハッシュ値、NewExp は遷移後の「推定残り手数」
		unsigned long long V1 = ((V >> t[px][py]) & 15ULL);
		unsigned long long V2 = ((V >> t[sx][sy]) & 15ULL);
		int nexExp = exp - dst[px][py][V1] - dst[sx][sy][V2] + dst[px][py][V2] + dst[sx][sy][V1];
		if (nexExp > dep - 1) continue;

		unsigned long long nexV = V + ((V2 - V1) << t[px][py]) + ((V1 - V2) << t[sx][sy]);
		bool ret = dfs(dep - 1, nexV, sx, sy, i, nexExp);
		if (ret == true) return true;
	}
	return false;
}

int main() {
	// 初期値
	unsigned long long InitV = 0;
	int Initpx, Initpy, Initexp = 0;

	// 入力など
	init();
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			unsigned long long pv; cin >> pv;
			InitV += (pv << t[i][j]);
			if (pv != 0) Initexp += dst[i][j][pv];
			if (pv == 0) { Initpx = i; Initpy = j; }
		}
	}

	// 0 手が最短の場合の例外処理
	if (Initexp == 0) {
		cout << "0" << endl;
		return 0;
	}

	// 探索
	for (int i = 1; i <= 80; i++) {
		bool I = dfs(i, InitV, Initpx, Initpy, -1, Initexp);
		if (I == true) { cout << i << endl; break; }
	}
	return 0;
}