#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define FOR(i,a,b) for(int i= (a); i<((int)b); ++i) #define RFOR(i,a) for(int i=(a); i >= 0; --i) #define FOE(i,a) for(auto i : a) #define ALL(c) (c).begin(), (c).end() #define DUMP(x) cerr << #x << " = " << (x) << endl; #define SUM(x) std::accumulate(ALL(x), 0L) #define EPS 1e-14 using namespace std; vector> target = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, {13, 14, 15, 0} }; // 右, 下, 左, 上(, 右上, 右下, 左下, 左上) vector dy = { 0, -1, 0, 1 }; //, 1, -1, -1, 1 }; vector dx = { 1, 0, -1, 0 }; // , 1, 1, -1, -1 }; bool dfs(vector> v, vector used) { if (v == target) { return true; } if (count(ALL(used), false) == 0) { return false; } FOR(i, 0, v.size()) { FOR(j, 0, v[0].size()) { if (v[i][j] != 0) { continue; } int now_y = i, now_x = j; for (int i = 0; i < dy.size(); i++) { int next_y = now_y + dy[i]; int next_x = now_x + dx[i]; if (0 <= next_y && next_y < v.size() && 0 <= next_x && next_x < v[0].size()) { int n = v[next_y][next_x]; if (used[n]) { continue; } used[n] = true; swap(v[next_y][next_x], v[now_y][now_x]); if (dfs(v, used)) { return true; } used[n] = false; swap(v[next_y][next_x], v[now_y][now_x]); } } } } return false; } int main(int argc, char *argv[]) { vector> v; int a, b, c, d; FOR(i, 0, 4) { cin >> a >> b >> c >> d; v.push_back({a, b, c, d}); } vector used(16, false); if (dfs(v, used)) { cout << "Yes" << endl; } else { cout << "No" << endl; } }