結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー Mao-beta
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0