結果
問題 |
No.228 ゆきこちゃんの 15 パズル
|
ユーザー |
![]() |
提出日時 | 2018-08-03 15:48:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 861 bytes |
コンパイル時間 | 1,402 ms |
コンパイル使用メモリ | 167,708 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-19 17:25:38 |
合計ジャッジ時間 | 2,114 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; //INSERT ABOVE HERE const Int N = 4; Int a[N][N],z[N][N]; void check(){ for(Int i=0;i<N;i++) for(Int j=0;j<N;j++) if(a[i][j]!=z[i][j]) return; cout<<"Yes"<<endl; exit(0); } Int di[]={1,-1,0,0}; Int dj[]={0,0,1,-1}; void dfs(Int b){ check(); for(Int i=0;i<N;i++){ for(Int j=0;j<N;j++){ if(a[i][j]) continue; for(Int k=0;k<4;k++){ Int ni=i+di[k],nj=j+dj[k]; if(ni<0||ni>=N||nj<0||nj>=N) continue; Int x=a[ni][nj]; if((b>>x)&1) continue; Int nb=b|(1<<x); swap(a[i][j],a[ni][nj]); dfs(nb); swap(a[i][j],a[ni][nj]); } } } } signed main(){ for(Int i=0;i<N;i++) for(Int j=0;j<N;j++) cin>>a[i][j]; for(Int i=0;i<N;i++) for(Int j=0;j<N;j++) z[i][j]=(i*N+j+1)%(N*N); dfs(0); cout<<"No"<<endl; return 0; }