結果
問題 | No.228 ゆきこちゃんの 15 パズル |
ユーザー |
![]() |
提出日時 | 2019-08-24 18:05:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,591 bytes |
コンパイル時間 | 1,737 ms |
コンパイル使用メモリ | 158,092 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 13:08:49 |
合計ジャッジ時間 | 1,862 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)x.size()) template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;} typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vi> vvi; const int inf = 1LL<<60; const int mod = 1e9 + 7; const double eps = 1e-9; /*{ }*/ int a[16], ans[16]; bool used[16]; bool check(int a[]){ rep(i, 0, 16) if(a[i] != i) return false; return true; } void dfs(){ if(check(a)){ rep(i, 0, 16) ans[i] = a[i]; return; } int zero; rep(i, 0, 16) if(a[i] == 15) zero = i; if(zero-4 >= 0 and !used[a[zero-4]]){ used[a[zero-4]] = true; swap(a[zero], a[zero-4]); dfs(); swap(a[zero], a[zero-4]); used[a[zero-4]] = false; } if(zero+4 < 16 and !used[a[zero+4]]){ used[a[zero+4]] = true; swap(a[zero], a[zero+4]); dfs(); swap(a[zero], a[zero+4]); used[a[zero+4]] = false; } if(zero%4 >= 1 and !used[a[zero-1]]){ used[a[zero-1]] = true; swap(a[zero], a[zero-1]); dfs(); swap(a[zero], a[zero-1]); used[a[zero-1]] = false; } if(zero%4 < 3 and !used[a[zero+1]]){ used[a[zero+1]] = true; swap(a[zero], a[zero+1]); dfs(); swap(a[zero], a[zero+1]); used[a[zero+1]] = false; } } signed main(){ rep(i, 0, 16){ cin >> a[i]; a[i] = (a[i] + 15) %16; } dfs(); cout << (check(ans) ? "Yes" : "No") << endl; return 0; }