結果
問題 | No.228 ゆきこちゃんの 15 パズル |
ユーザー |
|
提出日時 | 2015-06-19 23:00:48 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 33 ms / 5,000 ms |
コード長 | 883 bytes |
コンパイル時間 | 98 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-07-07 04:12:08 |
合計ジャッジ時間 | 1,530 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
def read_data(): a = [] for i in range(4): row = list(map(int, input().split())) a.append(row) return a def solve(a): init = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]] moved = [False] * 16 r, c = 3, 3 return dfs(a, init, moved, r, c) def dfs(goal, status, moved, r, c): if goal == status: return True for nr, nc in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]: if nr > 3 or nr < 0 or nc > 3 or nc < 0: continue num = status[nr][nc] if moved[num]: continue status[nr][nc] = 0 status[r][c] = num moved[num] = True if dfs(goal, status, moved, nr, nc): return True moved[num] = False status[r][c] = 0 status[nr][nc] = num return False a = read_data() if solve(a): print('Yes') else: print('No')