結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー bellangeldindon
提出日時 2019-04-26 15:14:39
言語 Python2
(2.7.18)
結果
AC  
実行時間 32 ms / 5,000 ms
コード長 1,592 bytes
コンパイル時間 619 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2024-11-24 12:33:00
合計ジャッジ時間 1,688 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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