結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー btk
提出日時 2015-06-19 23:07:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,685 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 107,624 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 04:13:22
合計ジャッジ時間 1,562 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;


#define input_init stringstream ss; string strtoken, token; istringstream is
#define input_line  getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit)
#define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num

typedef vector<int> VI;
typedef vector<VI> VVI;
const int dir[] = { 0, -1, 0, 1, 0 };
typedef pair<VVI,int> P;

#define mp(a,b) make_pair(a,b)


void cp(VVI& d, VVI& s){
	for (int i = 1; i < 5; i++)
		for (int j = 1; j < 5; j++)
			d[i][j] = s[i][j];
}
int main(void){
	map<VVI,list<int>> memo;
	auto a = mp(VVI(6, VI(6, 16)), 1 << 16);
	for (int i = 1; i < 5; i++){
		for (int j = 1; j < 5; j++){
			a.first[i][j] = ((i - 1) * 4 + j)%16;
		}
	}
	queue<P> que;
	que.push(a);
	memo[a.first].push_back(a.second);
	return 0;
	while (que.empty() == false){
		auto v = que.front(); que.pop();
		int x, y;
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				if (v.first[i][j] == 0)x = i, y = j;
		int cnt = 0;
		for (int i = 1; i < 16; i++)
			cnt += ((v.second&(1 << i)) > 0);
		if (cnt >= 9)continue;
		
		for (int i = 0; i < 5; i++){
			int xx = x + dir[i];
			int yy = y + dir[i + 1];
			if ((v.second&(1<<v.first[xx][yy])) == 0){
				auto u = mp(VVI(6, VI(6, 16)),v.second);
				cp(u.first, v.first);
				u.second+=1<<v.first[xx][yy];
				swap(u.first[xx][yy], u.first[x][y]);
				memo[u.first].push_back(u.second);
				que.push(u);
			}
		}
	}
	for (int i = 1; i < 5; i++){
		for (int j = 1; j < 5; j++){
			cin >> a.first[i][j];
		}
	}
	que.push(a);
	while (que.empty() == false){
		auto v = que.front(); que.pop();
		if (memo.count(v.first) > 0){
			for (auto &it : memo[v.first]){
				if ((v.second&it) == (1 << 16)){
					cout << "Yes" << endl;
					return 0;
				}
			}
		}
		int x, y;
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				if (v.first[i][j] == 0)x = i, y = j;
		int cnt = 0;
		for (int i = 1; i < 16; i++)
			cnt += ((v.second&(1 << i)) > 0);
		if (cnt >= 9)continue;

		for (int i = 0; i < 5; i++){
			int xx = x + dir[i];
			int yy = y + dir[i + 1];
			if ((v.second&(1 << v.first[xx][yy])) == 0){
				auto u = mp(VVI(6, VI(6, 16)), v.second);
				cp(u.first, v.first);
				u.second += 1 << v.first[xx][yy];
				swap(u.first[xx][yy], u.first[x][y]);
				que.push(u);
			}
		}
	}
	cout << "No" << endl;
	return(0);
}
0