結果
問題 |
No.228 ゆきこちゃんの 15 パズル
|
ユーザー |
|
提出日時 | 2025-02-11 11:25:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 68 ms / 5,000 ms |
コード長 | 1,288 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 82,104 KB |
実行使用メモリ | 72,988 KB |
最終ジャッジ日時 | 2025-02-11 11:25:54 |
合計ジャッジ時間 | 2,324 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
import sys import math import bisect from heapq import heapify, heappop, heappush from collections import deque, defaultdict, Counter from functools import lru_cache from itertools import accumulate, combinations, permutations, product sys.set_int_max_str_digits(10 ** 6) sys.setrecursionlimit(1000000) MOD = 10 ** 9 + 7 MOD99 = 998244353 input = lambda: sys.stdin.readline().strip() NI = lambda: int(input()) NMI = lambda: map(int, input().split()) NLI = lambda: list(NMI()) SI = lambda: input() SMI = lambda: input().split() SLI = lambda: list(SMI()) EI = lambda m: [NLI() for _ in range(m)] def main(): A = EI(4) B = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]] DH = [1, -1, 0, 0] DW = [0, 0, 1, -1] def rec(h, w, state): if A == B: print("Yes") exit() for dh, dw in zip(DH, DW): nh = h + dh nw = w + dw if 0 <= nh < 4 and 0 <= nw < 4: x = B[nh][nw] if (state >> x) & 1: continue B[nh][nw], B[h][w] = B[h][w], B[nh][nw] rec(nh, nw, state | (1 << x)) B[nh][nw], B[h][w] = B[h][w], B[nh][nw] rec(3, 3, 0) print("No") if __name__ == "__main__": main()