結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー btkbtk
提出日時 2015-06-19 23:07:01
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,685 bytes
コンパイル時間 939 ms
コンパイル使用メモリ 105,092 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-21 10:07:07
合計ジャッジ時間 2,011 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

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