#include #include #include #include #include #include #include #include using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define array2(type, x, y) array, x> #define vector2(type) vector > #define out(...) //printf(__VA_ARGS__) typedef pair pos; int pos::*x = &pos::first; int pos::*y = &pos::second; int dxy[] = {0, 1, 0, -1, 0}; /*================================*/ int m[4][4]; bool isOK(int ma[4][4]) { REP(y,4) REP(x,4) { if (m[x][y] != ma[x][y]) return false; } return true; } void copy(int m1[4][4], int m2[4][4]) { REP(y,4) REP(x,4) m2[x][y] = m1[x][y]; } bool dp(int ma[4][4], vector moved) { if (isOK(ma)) return true; bool ok = false; pos c; REP(y,4) REP(x,4) { if (ma[x][y] == 0) { c.first = x; c.second = y; break; } } REP(i,4) { int mc[4][4]; copy(ma, mc); int nx = c.first + dxy[i]; int ny = c.second + dxy[i+1]; if (nx < 0 || 4 <= nx) continue; if (ny < 0 || 4 <= ny) continue; if (CONTAIN(moved, ma[nx][ny])) continue; // 移動 swap(mc[c.*x][c.*y], mc[nx][ny]); // コピーして移動済みに追加 vector movedc; copy(ALL(moved), back_inserter(movedc)); movedc.push_back(ma[nx][ny]); // 次へ ok |= dp(mc, movedc); } return ok; } signed main() { REP(y,4) REP(x,4) cin >> m[x][y]; int ma[4][4]; int i = 1; REP(y,4) REP(x,4) { ma[x][y] = i % 16; i++; } vector moved; bool ok = dp(ma, moved); cout << (ok ? "Yes" : "No") << endl; return 0; }