#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define input_init stringstream ss; string strtoken, token; istringstream is #define input_line getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit) #define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num 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++) cnt += ((v.second&(1 << i)) > 0); if (cnt >= 9)continue; for (int i = 0; i < 5; i++){ int xx = x + dir[i]; int yy = y + dir[i + 1]; if ((v.second&(1<> a.first[i][j]; } } 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 >= 9)continue; for (int i = 0; i < 5; i++){ int xx = x + dir[i]; int yy = y + dir[i + 1]; if ((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); }