結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー bellangeldindonbellangeldindon
提出日時 2019-04-26 15:14:39
言語 Python2
(2.7.18)
結果
AC  
実行時間 34 ms / 5,000 ms
コード長 1,592 bytes
コンパイル時間 42 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-05-03 12:37:33
合計ジャッジ時間 1,326 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
6,816 KB
testcase_01 AC 10 ms
6,940 KB
testcase_02 AC 15 ms
6,944 KB
testcase_03 AC 32 ms
6,940 KB
testcase_04 AC 9 ms
6,944 KB
testcase_05 AC 9 ms
6,944 KB
testcase_06 AC 27 ms
6,944 KB
testcase_07 AC 20 ms
6,944 KB
testcase_08 AC 13 ms
6,940 KB
testcase_09 AC 21 ms
6,944 KB
testcase_10 AC 23 ms
6,940 KB
testcase_11 AC 31 ms
6,940 KB
testcase_12 AC 31 ms
6,940 KB
testcase_13 AC 30 ms
6,940 KB
testcase_14 AC 26 ms
6,944 KB
testcase_15 AC 30 ms
6,944 KB
testcase_16 AC 27 ms
6,940 KB
testcase_17 AC 25 ms
6,940 KB
testcase_18 AC 31 ms
6,940 KB
testcase_19 AC 28 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def puzzledone(lst):
	for i in range(0, 4):
		for j in range(0, 4):
			p = (i*4 + j+1) % 16
			if p != lst[i][j]: return False
	return True

puzzle = []
for i in range(0, 4):
	puzzle.append(map(int, raw_input().split()))
dh = -1
dw = -1
for i in range(0, 4):
	for j in range(0, 4):
		if puzzle[i][j] == 0:
			dh = i
			dw = j
			break
	if dh != -1: break
status = [False]
for i in range(0, 15):
	status.append(True)
stack = [[dh, dw, puzzle, status]]
flag = False
while stack != []:
	now = stack.pop(-1)
	if puzzledone(now[2]):
		flag = True
		break
	h = now[0]
	w = now[1]
	for i in range(0, 2):
		nexth = h - 1 + 2*i
		if 0 <= nexth and nexth < 4:
			if now[3][now[2][nexth][w]]:
				nextstatus = []
				for j in range(0, 16):
					nextstatus.append(now[3][j])
				nextstatus[now[2][nexth][w]] = False
				nextpuzzle = []
				for j in range(0, 4):
					lst = []
					for k in range(0, 4):
						lst.append(now[2][j][k])
					nextpuzzle.append(lst)
				nextpuzzle[h][w] = nextpuzzle[nexth][w]
				nextpuzzle[nexth][w] = 0
				stack.append([nexth, w, nextpuzzle, nextstatus])
		nextw = w - 1 + 2*i
		if 0 <= nextw and nextw < 4:
			if now[3][now[2][h][nextw]]:
				nextstatus = []
				for j in range(0, 16):
					nextstatus.append(now[3][j])
				nextstatus[now[2][h][nextw]] = False
				nextpuzzle = []
				for j in range(0, 4):
					lst = []
					for k in range(0, 4):
						lst.append(now[2][j][k])
					nextpuzzle.append(lst)
				nextpuzzle[h][w] = nextpuzzle[h][nextw]
				nextpuzzle[h][nextw] = 0
				stack.append([h, nextw, nextpuzzle, nextstatus])
if flag: print "Yes"
else: print "No"
0