結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー kongarishisyamo
提出日時 2016-02-28 04:20:26
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,034 bytes
コンパイル時間 584 ms
コンパイル使用メモリ 59,240 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-24 11:58:33
合計ジャッジ時間 1,474 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<iostream>
#include<algorithm>

using namespace std;

int main(){

	int a[4][4];
	bool f[16];

	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=15;i++) f[i]=true;

	while(1){
		bool fm=true;
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				//cout<<a[i][j]<<",";
				if(i==3&&j==3){
					if(a[i][j]!=0) fm=false;
					break;
				}
				if(a[i][j]!=i*4+j+1) fm=false;
			}
			//cout<<endl;
		}
		if(fm){
			cout<<"Yes"<<endl;
			break;
		}
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				if(a[i][j]==0){
					int dx[]={0,0,1,-1};
					int dy[]={1,-1,0,0};
					for(int k=0;k<4;k++){
						if(j+dx[k]>=0&&j+dx[k]<4&&i+dy[k]>=0&&i+dy[k]<4&&a[i+dy[k]][j+dx[k]]==i*4+j+1&&f[a[i+dy[k]][j+dx[k]]]){
							f[a[i+dy[k]][j+dx[k]]]=false;
							swap(a[i][j],a[i+dy[k]][j+dx[k]]);
							i=3;
							j=3;
							k=3;
							//cout<<k<<","<<i<<","<<j<<","<<i+dy[k]<<","<<j+dx[k]<<endl;
						}
						else if(k==3){
							cout<<"No"<<endl;
							return 0;
						}
					}
				}
			}
		}
	}

}
0