#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef vector VI; typedef vector VVI; const int dir[] = { 0, -1, 0, 1, 0 }; typedef pair P; #define mp(a,b) make_pair(a,b) void cp(VVI& d, VVI& s){ for (int i = 1; i < 5; i++) for (int j = 1; j < 5; j++) d[i][j] = s[i][j]; } int main(void){ map> memo; auto a = mp(VVI(6, VI(6, 16)), 1 << 16); for (int i = 1; i < 5; i++){ for (int j = 1; j < 5; j++){ a.first[i][j] = ((i - 1) * 4 + j)%16; } } queue

que; //que.push(a); memo[a.first].push_back(a.second); /* while (que.empty() == false){ auto v = que.front(); que.pop(); int x, y; for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if (v.first[i][j] == 0)x = i, y = j; int cnt = 0; for (int i = 1; i < 16; i++) if (((v.second&(1 << i)) > 0))cnt++; if (cnt >= 9) continue; for (int i = 0; i < 5; i++){ int xx = x + dir[i]; int yy = y + dir[i + 1]; if (v.first[xx][yy]<16&&(v.second&(1<> a.first[i][j]; } } a.second = (1 << 16); que.push(a); while (que.empty() == false){ auto v = que.front(); que.pop(); if (memo.count(v.first) > 0){ for (auto &it : memo[v.first]){ if ((v.second&it) == (1 << 16)){ cout << "Yes" << endl; return 0; } } } int x, y; for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if (v.first[i][j] == 0)x = i, y = j; int cnt = 0; for (int i = 1; i < 16; i++) cnt += ((v.second&(1 << i)) > 0); if (cnt >= 17) continue; for (int i = 0; i < 5; i++){ int xx = x + dir[i]; int yy = y + dir[i + 1]; if (v.first[xx][yy]<16 && (v.second&(1 << v.first[xx][yy])) == 0){ auto u = mp(VVI(6, VI(6, 16)), v.second); cp(u.first, v.first); u.second |= (1 << v.first[xx][yy]); swap(u.first[xx][yy], u.first[x][y]); que.push(u); } } } cout << "No" << endl; return(0); }