結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー bellangeldindonbellangeldindon
提出日時 2019-04-26 15:14:39
言語 Python2
(2.7.18)
結果
AC  
実行時間 33 ms / 5,000 ms
コード長 1,592 bytes
コンパイル時間 899 ms
コンパイル使用メモリ 7,112 KB
実行使用メモリ 6,068 KB
最終ジャッジ日時 2023-08-16 03:01:31
合計ジャッジ時間 2,101 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
5,984 KB
testcase_01 AC 10 ms
5,932 KB
testcase_02 AC 16 ms
5,848 KB
testcase_03 AC 32 ms
5,852 KB
testcase_04 AC 10 ms
6,032 KB
testcase_05 AC 10 ms
5,856 KB
testcase_06 AC 31 ms
5,928 KB
testcase_07 AC 22 ms
6,068 KB
testcase_08 AC 14 ms
5,880 KB
testcase_09 AC 24 ms
5,856 KB
testcase_10 AC 26 ms
5,884 KB
testcase_11 AC 32 ms
6,020 KB
testcase_12 AC 32 ms
5,936 KB
testcase_13 AC 33 ms
5,856 KB
testcase_14 AC 27 ms
5,928 KB
testcase_15 AC 32 ms
6,044 KB
testcase_16 AC 29 ms
5,856 KB
testcase_17 AC 26 ms
5,928 KB
testcase_18 AC 32 ms
5,932 KB
testcase_19 AC 26 ms
5,852 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