結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー togari_takamoto
提出日時 2015-06-20 13:24:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,219 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 415 ms
コンパイル使用メモリ 57,476 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 15:11:45
合計ジャッジ時間 1,178 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:23: warning: ‘y_zero’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |         cout << (recur(table, used, x_zero, y_zero) ? "Yes" : "No") << endl;
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:61:23: warning: ‘x_zero’ may be used uninitialized in this function [-Wmaybe-uninitialized]

ソースコード

diff #
raw source code 

#include <iostream>
#include <array>

using namespace std;
using Table = array<array<int, 6>, 6>;

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

bool recur(const Table & table, const array<bool, 16> & used, int x, int y){
	bool is_finish = true;

	for (size_t y = 1; y < 5; y++){
		for (size_t x = 1; x < 5; x++){
			if (y==4 && x==4) continue;
			if (table[x][y] != x + (y - 1) * 4) is_finish = false;
		}
	}
	if (is_finish) return true;

	for (size_t i = 0; i < 4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (table[nx][ny] != -1 && !used[table[nx][ny]]){
			auto nt = table;
			nt[x][y] = table[nx][ny];
			nt[nx][ny] = 0;
			auto nu = used;
			nu[table[nx][ny]] = true;
			
			if(recur(nt, nu, nx, ny)) return true;
		}
	}
	return false;
}

int main(){
	Table table;
	for (size_t i = 0; i < 6; i++){
		table[i][0] = -1;
		table[i][5] = -1;
		table[0][i] = -1;
		table[5][i] = -1;
	}

	int x_zero, y_zero;

	for (size_t y = 1; y < 5; y++){
		for (size_t x = 1; x < 5; x++){
			cin >> table[x][y];
			if (table[x][y] == 0){
				x_zero = x;
				y_zero = y;
			}
		}
	}

	array<bool, 16> used;
	used.fill(false);

	cout << (recur(table, used, x_zero, y_zero) ? "Yes" : "No") << endl;

	return 0;
}
0