結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:33:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,912 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,480 KB
実行使用メモリ 54,196 KB
最終ジャッジ日時 2025-06-12 16:33:22
合計ジャッジ時間 1,653 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    # Initialize the positions for the initial configuration
    initial_pos = {}
    nums = list(range(1, 16)) + [0]
    idx = 0
    for i in range(4):
        for j in range(4):
            num = nums[idx]
            initial_pos[num] = (i, j)
            idx += 1

    # Read the target configuration
    target = []
    zero_pos = None
    target_pos = {}
    for i in range(4):
        row = list(map(int, input().split()))
        target.append(row)
        for j in range(4):
            num = row[j]
            if num == 0:
                zero_pos = (i, j)
            else:
                target_pos[num] = (i, j)

    # Check if all pieces (1-15) have moved at most one tile
    possible = True
    for num in range(1, 16):
        ix, iy = initial_pos[num]
        if num not in target_pos:
            possible = False
            break
        tx, ty = target_pos[num]
        dx = abs(ix - tx)
        dy = abs(iy - ty)
        if dx + dy > 1:
            possible = False
            break
    if not possible:
        print("No")
        return

    # Calculate inversion count of the target configuration (excluding 0)
    flat = []
    for row in target:
        for num in row:
            if num != 0:
                flat.append(num)

    def count_inversion(arr):
        inv = 0
        n = len(arr)
        for i in range(n):
            for j in range(i + 1, n):
                if arr[i] > arr[j]:
                    inv += 1
        return inv

    target_inversion = count_inversion(flat)

    # Calculate row distance of the empty tile
    initial_zero_row = 3  # initial zero is at row 3 (0-based)
    target_zero_row = zero_pos[0]
    row_distance = abs(initial_zero_row - target_zero_row)

    # Check solvability condition
    if (target_inversion + row_distance) % 2 == 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()
0