結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー btkbtk
提出日時 2015-06-19 23:35:39
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,558 bytes
コンパイル時間 1,017 ms
コンパイル使用メモリ 112,568 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-07 04:22:32
合計ジャッジ時間 1,795 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 WA -
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:108:29: warning: ‘y’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |                         int yy = y + dir[i + 1];
      |                             ^~
main.cpp:107:29: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |                         int xx = x + dir[i];
      |                             ^~

ソースコード

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;


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);
	/*
	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++)
			if (((v.second&(1 << i)) > 0))cnt++;
		if (cnt >= 9)
			continue;
		
		for (int i = 0; i < 5; i++){
			int xx = x + dir[i];
			int yy = y + dir[i + 1];
			if (v.first[xx][yy]<16&&(v.second&(1<<v.first[xx][yy])) == 0){
				P u;
				u.first.resize(6);
				for (auto &it : u.first){
					it.resize(6);
					for (auto &jt : it)jt = 16;
				}
				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];
		}
	}
	a.second = (1 << 16);
	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.first[xx][yy]<16 && (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