結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー beet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0