結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー btkbtk
提出日時 2015-06-20 00:07:34
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 2,674 bytes
コンパイル時間 1,388 ms
コンパイル使用メモリ 115,864 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 04:29:58
合計ジャッジ時間 1,915 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
6,812 KB
testcase_01 AC 3 ms
6,816 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 5 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 3 ms
6,944 KB
testcase_12 AC 5 ms
6,940 KB
testcase_13 AC 5 ms
6,940 KB
testcase_14 AC 4 ms
6,944 KB
testcase_15 AC 4 ms
6,940 KB
testcase_16 AC 4 ms
6,940 KB
testcase_17 AC 4 ms
6,940 KB
testcase_18 AC 4 ms
6,944 KB
testcase_19 AC 5 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:109:29: warning: ‘y’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |                         int yy = y + dir[i + 1];
      |                             ^~
main.cpp:108:29: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |                         int xx = x + dir[i];
      |                             ^~
main.cpp:60:29: warning: ‘y’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |                         int yy = y + dir[i + 1];
      |                             ^~
main.cpp:59:29: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |                         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 < 4; 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 = v.second;
				u.second |= (1 << v.first[xx][yy]);
				swap(u.first[xx][yy], u.first[x][y]);
				//if (memo.count(u.first) == 0)memo.insert(memo.begin(), mp(u.first, list<int>()));
				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 >= 17)
			continue;

		for (int i = 0; i < 4; 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