結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

#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