結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:35:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 85 ms / 5,000 ms
コード長 4,103 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 78,312 KB
最終ジャッジ日時 2025-06-12 16:36:00
合計ジャッジ時間 2,316 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def read_input():
    grid = []
    for _ in range(4):
        row = list(map(int, sys.stdin.readline().split()))
        grid.append(row)
    return grid

def initial_grid():
    grid = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 0]
    ]
    return grid

def calculate_inversions_and_empty_pos(grid, n=4):
    flat = []
    empty_pos = None
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                empty_pos = (i, j)
            else:
                flat.append(grid[i][j])
    inversions = 0
    for i in range(len(flat)):
        for j in range(i+1, len(flat)):
            if flat[i] > flat[j]:
                inversions += 1
    return inversions, empty_pos

def is_solvable(initial_inversions, initial_empty_row, target_inversions, target_empty_row):
    initial_parity = (initial_inversions + initial_empty_row) % 2
    target_parity = (target_inversions + target_empty_row) % 2
    return initial_parity == target_parity

def main():
    target = read_input()
    initial = initial_grid()

    # Check if target is same as initial (trivial case)
    if target == initial:
        print("Yes")
        return

    # Compute inversion and empty position for initial and target
    initial_flat = [initial[i][j] for i in range(4) for j in range(4)]
    target_flat = [target[i][j] for i in range(4) for j in range(4)]

    # Function to compute inversion and empty position
    def compute_inversion_and_empty(g):
        inv = 0
        empty_pos = -1
        for i in range(16):
            if g[i] == 0:
                empty_pos = i
                continue
            for j in range(i+1, 16):
                if g[j] != 0 and g[i] > g[j]:
                    inv += 1
        empty_row = empty_pos // 4
        return inv, empty_row

    initial_inversions, initial_empty_row = compute_inversion_and_empty(initial_flat)
    target_inversions, target_empty_row = compute_inversion_and_empty(target_flat)

    # Check standard solvability condition
    if (initial_inversions + initial_empty_row) % 2 != (target_inversions + target_empty_row) % 2:
        print("No")
        return

    # Now perform BFS with state tracking including moved tiles
    # Each state is a tuple (grid, moved_tiles_set, empty_pos)
    initial_state = []
    for i in range(4):
        for j in range(4):
            initial_state.append(initial[i][j])
    initial_state = tuple(initial_state)
    initial_moved = frozenset()
    initial_empty_pos = (3, 3)  # Starting position of empty in initial state

    target_state = []
    for i in range(4):
        for j in range(4):
            target_state.append(target[i][j])
    target_state = tuple(target_state)

    visited = set()
    queue = deque()
    queue.append((initial_state, initial_moved, initial_empty_pos))

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        current, moved, empty = queue.popleft()
        if current == target_state:
            print("Yes")
            return
        if (current, moved) in visited:
            continue
        visited.add((current, moved))

        # Find position of empty
        empty_i, empty_j = empty
        for di, dj in directions:
            ni, nj = empty_i + di, empty_j + dj
            if 0 <= ni < 4 and 0 <= nj < 4:
                tile = current[ni * 4 + nj]
                if tile != 0 and tile not in moved:
                    new_moved = set(moved)
                    new_moved.add(tile)
                    new_moved = frozenset(new_moved)
                    new_state = list(current)
                    # Swap empty with the tile
                    new_state[ni * 4 + nj] = 0
                    new_state[empty_i * 4 + empty_j] = tile
                    new_state = tuple(new_state)
                    new_empty_pos = (ni, nj)
                    if (new_state, new_moved) not in visited:
                        queue.append((new_state, new_moved, new_empty_pos))

    print("No")

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