結果
問題 |
No.228 ゆきこちゃんの 15 パズル
|
ユーザー |
|
提出日時 | 2024-11-04 10:14:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 247 ms / 5,000 ms |
コード長 | 859 bytes |
コンパイル時間 | 468 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 83,088 KB |
最終ジャッジ日時 | 2024-11-04 10:14:35 |
合計ジャッジ時間 | 6,528 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
from collections import deque import copy dist = {} x = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0) goal = set() goal.add(x) x = list(x) x = [[x[i],0] for i in range(16)] que = deque([x]) while que: x = que.popleft() x1 = tuple([x[i][0] for i in range(16)]) # print(x1) ind = x.index([0,0]) h = ind//4 w = ind%4 for dh,dw in [(0,1),(0,-1),(1,0),(-1,0)]: nh = h+dh nw = w+dw if 0<=nh<4 and 0<=nw<4: y = copy.deepcopy(x) ind1 = nh*4+nw if y[ind1][1]==0: y[ind],y[ind1] = y[ind1],y[ind] y[ind][1] = 1 z = tuple([y[i][0] for i in range(16)]) goal.add(z) que.append(y) y = [] for i in range(4): y += list(map(int,input().split())) y = tuple(y) if y in goal: print("Yes") else: print("No")