#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int DY[4] = {-1, 0, 0, 1}; const int DX[4] = { 0,-1, 1, 0}; int correctField[4][4] = { { 1, 2, 3, 4}, { 5, 6, 7, 8}, { 9,10,11,12}, {13,14,15, 0} }; int field[4][4]; map checkList; bool check(){ for(int y = 0; y < 4; y++){ for(int x = 0; x < 4; x++){ if(correctField[y][x] != field[y][x]){ return false; } } } return true; } bool success; bool isOutside(int y, int x){ return (y < 0 || 4 <= y || x < 0 || 4 <= x); } void dfs(int y, int x){ if(y == 3 && x == 3 && check()){ success = true; } for(int i = 0; i < 4; i++){ int ny = y + DY[i]; int nx = x + DX[i]; if (isOutside(ny,nx)) continue; int num = field[ny][nx]; if (checkList[num]) continue; checkList[num] = true; field[ny][nx] = field[y][x]; field[y][x] = num; dfs(ny, nx); checkList[num] = false; field[y][x] = field[ny][nx]; field[ny][nx] = num; } } int main(){ int curY = 0; int curX = 0; for(int y = 0; y < 4; y++){ for(int x = 0; x < 4; x++){ cin >> field[y][x]; if (field[y][x] == 0){ curY = y; curX = x; } } } success = false; dfs(curY, curX); if (success) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }