FunOfSearching-9-2.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct State {
	int c[4][4];
};

bool operator<(const State& a1, const State& a2) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (a1.c[i][j] < a2.c[i][j]) return true;
			if (a1.c[i][j] > a2.c[i][j]) return false;
		}
	}
	return false;
}

bool operator==(const State& a1, const State& a2) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (a1.c[i][j] < a2.c[i][j]) return false;
			if (a1.c[i][j] > a2.c[i][j]) return false;
		}
	}
	return true;
}

State Initial, Final;
vector<State> V;
vector<State> W1;
vector<State> W2;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void tansaku(int dep, State S, int prevdir) {
	if (dep == 0) { V.push_back(S); return; }

	int px = 0, py = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (S.c[i][j] == 0) { px = i; py = j; }
		}
	}

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

		State NewS = S;
		swap(NewS.c[sx][sy], NewS.c[px][py]);
		tansaku(dep - 1, NewS, i);
	}
}

bool solve(int moves) {
	// 再帰関数を用いた全探索で W1, W2 を求める
	W1.clear();
	W2.clear();
	V.clear(); tansaku(moves / 2, Initial, -1); W1 = V;
	V.clear(); tansaku(moves - (moves / 2), Final, -1); W2 = V;

	// W1, W2 をソート
	sort(W1.begin(), W1.end());
	sort(W2.begin(), W2.end());

	// W1[i] = W2[j] となる (i, j) が存在するか判定
	for (int i = 0; i < (int)W1.size(); i++) {
		int pos1 = lower_bound(W2.begin(), W2.end(), W1[i]) - W2.begin();
		if (pos1 < (int)W2.size() && W1[i] == W2[pos1]) return true;
	}
	return false;
}

int main() {
	// 入力など
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) Final.c[i][j] = (i * 4 + j + 1) % 16;
	}
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) cin >> Initial.c[i][j];
	}

	// 答えを求める
	for (int i = 0; i <= 80; i++) {
		bool I = solve(i);
		if (I == true) { cout << i << endl; break; }
	}
	return 0;
}