結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー IL_msta
提出日時 2015-06-20 03:57:02
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,588 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 88,572 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 04:37:24
合計ジャッジ時間 1,463 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>

#include <algorithm>
#include <cmath>

#include <string>
#include <list>
#include <queue>
#include <vector>
#include <complex>

/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) std::cout<<(p)<<std::endl;
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////
struct ban{
	int n[4][4];
	bool b[16];
	int wh;
};
int A[16];
bool sol(ban b){
	int ans = 0;
	rep(i,16){
		if(A[i] == b.n[i/4][i%4]){
			++ans;
		}
	}
	if(ans == 16){
		return true;
	}
	return false;
}
int main(void){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(6);//
	int aaa;
	rep(i,16){
		cin>>aaa;
		A[i] = (aaa+15)%16;
	}

	ban b,temp,cop;
	rep(i,16){
		b.n[i/4][i%4] = i;
		b.b[i] = true;
	}
	b.wh=15;

	if(sol(b) == true){
		P("Yes");
		return 0;
	}

	queue<ban> qu;
	qu.push(b);
	int dx[4] = {  1,  0, -1,  0};
	int dy[4] = {  0,  1,  0, -1};
	
	int nx,ny;

	while(!qu.empty()){
		cop = qu.front();
		qu.pop();
		for(int i=0;i<4;++i){
			temp = cop;
			nx = (temp.wh)%4 + dx[i];
			ny = (temp.wh)/4 + dy[i];
			if( 0 <= nx && nx < 4 &&
				0 <= ny && ny < 4 &&
				temp.b[ temp.n[ ny ][ nx ] ] == true
				){
				temp.b[ temp.n[ ny ][ nx ] ] = false;
				temp.n[ (temp.wh)/4 ][ (temp.wh)%4 ] = temp.n[ ny ][ nx ];
				temp.n[ ny ][ nx ] = 15;
				temp.wh = (ny)*4 + nx;
				if( sol(temp) == true){
					P("Yes");
					return 0;
				}
				qu.push(temp);
			}
		}

	}
	P("No");
	return 0;
}
0