結果

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

ソースコード

diff # 

# Read the target grid
grid = []
for _ in range(4):
    row = list(map(int, input().split()))
    grid.append(row)

# Create a dictionary to store the position of each number in the target grid
target_pos = {}
for i in range(4):
    for j in range(4):
        v = grid[i][j]
        target_pos[v] = (i + 1, j + 1)  # 1-based coordinates

# Check if all numbers from 1 to 15 are present (input is valid)
valid = True
for v in range(1, 16):
    if v not in target_pos:
        valid = False
        break
if 0 not in target_pos:
    valid = False

if not valid:
    print("No")
    exit()

# Calculate inversion count of the target configuration (excluding 0)
flattened = []
for i in range(4):
    for j in range(4):
        v = grid[i][j]
        if v != 0:
            flattened.append(v)

inv_count = 0
n = len(flattened)
for i in range(n):
    for j in range(i + 1, n):
        if flattened[i] > flattened[j]:
            inv_count += 1

# Calculate Manhattan distance of the empty tile from its initial position (4,4)
zero_r, zero_c = target_pos[0]
manhattan_zero = abs(4 - zero_r) + abs(4 - zero_c)

# Check standard solvability condition
normal_condition = (inv_count + manhattan_zero) % 2 == 0

# Check each tile's Manhattan distance from its initial position
possible = True
for v in range(1, 16):
    # Initial position calculation (1-based)
    initial_row = (v - 1) // 4 + 1
    initial_col = (v - 1) % 4 + 1
    # Target position
    target_r, target_c = target_pos[v]
    dx = abs(target_r - initial_row)
    dy = abs(target_c - initial_col)
    if dx + dy > 1:
        possible = False
        break

# Determine the result
if normal_condition and possible:
    print("Yes")
else:
    print("No")
0