結果
問題 |
No.228 ゆきこちゃんの 15 パズル
|
ユーザー |
![]() |
提出日時 | 2025-03-06 16:36:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 50 ms / 5,000 ms |
コード長 | 1,911 bytes |
コンパイル時間 | 540 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 63,560 KB |
最終ジャッジ日時 | 2025-03-06 16:36:59 |
合計ジャッジ時間 | 2,388 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
import sys sys.setrecursionlimit(10**8) A = [] for i in range(4): a = list(map(int, input().split())) A.extend(a) # 全部書き出す def dfs(banmen:list, done:list, i:int): # i は空マスの位置 if banmen == A: exit(print('Yes')) return # 左 if i%4 != 0: # 空ますは i-1 になる # done に banmen[i - 1] を追加する target = banmen[i - 1] # 動かしてないなら動かす if not done[target]: banmen[i - 1], banmen[i] = banmen[i], banmen[i - 1] done[target] = True dfs(banmen, done, i - 1) done[target] = False banmen[i - 1], banmen[i] = banmen[i], banmen[i - 1] # 右 if i%4 != 3: target = banmen[i + 1] # 動かしてないなら動かす if not done[target]: banmen[i + 1], banmen[i] = banmen[i], banmen[i + 1] done[target] = True dfs(banmen, done, i + 1) done[target] = False banmen[i + 1], banmen[i] = banmen[i], banmen[i + 1] # 上 if i >= 4: target = banmen[i - 4] # 動かしてないなら動かす if not done[target]: banmen[i - 4], banmen[i] = banmen[i], banmen[i - 4] done[target] = True dfs(banmen, done, i - 4) done[target] = False banmen[i - 4], banmen[i] = banmen[i], banmen[i - 4] # 下 if i <= 11: target = banmen[i + 4] # 動かしてないなら動かす if not done[target]: banmen[i + 4], banmen[i] = banmen[i], banmen[i + 4] done[target] = True dfs(banmen, done, i + 4) done[target] = False banmen[i + 4], banmen[i] = banmen[i], banmen[i + 4] return shoki = [i%16 for i in range(1, 17)] done = [False]*16 dfs(shoki, done, 15) print('No')