結果

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

ソースコード

diff # 

import sys
from itertools import permutations
from collections import deque

def main():
    # Read input and setup initial and target positions
    initial_pos = {}
    target_pos = {}
    zero_initial = (3, 3)  # Initial empty position (0-based)
    zero_target = None

    # Initialize initial positions (standard 15-puzzle)
    cnt = 1
    for i in range(4):
        for j in range(4):
            if cnt <= 15:
                initial_pos[cnt] = (i, j)
                cnt += 1

    # Read target configuration
    target = []
    for i in range(4):
        row = list(map(int, sys.stdin.readline().split()))
        for j, num in enumerate(row):
            if num == 0:
                zero_target = (i, j)
            else:
                target_pos[num] = (i, j)
        target.extend(row)

    # Check standard solvability condition
    target_list = [num for num in target if num != 0]
    inv_count = 0
    for i in range(len(target_list)):
        for j in range(i+1, len(target_list)):
            if target_list[i] > target_list[j]:
                inv_count += 1

    row_initial = zero_initial[0]
    row_target = zero_target[0]
    row_diff = row_initial - row_target

    if (inv_count % 2) != (abs(row_diff) % 2):
        print("No")
        return

    # Check Manhattan distance for each tile
    possible = True
    for num in range(1, 16):
        if num not in initial_pos or num not in target_pos:
            continue
        ix, iy = initial_pos[num]
        tx, ty = target_pos[num]
        if abs(ix - tx) + abs(iy - ty) > 1:
            possible = False
            break
    if not possible:
        print("No")
        return

    # Collect pieces that need to be moved
    move_pieces = []
    for num in range(1, 16):
        if initial_pos[num] != target_pos[num]:
            move_pieces.append(num)

    if not move_pieces:
        print("Yes")
        return

    # BFS function to check path from current empty to target position avoiding obstacles
    def bfs(start, goal, obstacles):
        visited = [[False]*4 for _ in range(4)]
        q = deque()
        q.append((start[0], start[1]))
        visited[start[0]][start[1]] = True
        dirs = [(-1,0), (1,0), (0,-1), (0,1)]
        while q:
            x, y = q.popleft()
            if (x, y) == goal:
                return True
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < 4 and 0 <= ny < 4:
                    if not visited[nx][ny] and (nx, ny) not in obstacles:
                        visited[nx][ny] = True
                        q.append((nx, ny))
        return False

    # Check each permutation of move_pieces
    for perm in permutations(move_pieces):
        current_empty = zero_initial
        moved = set()
        valid = True
        for piece in perm:
            init_x, init_y = initial_pos[piece]
            # Possible adjacent positions to the piece's initial position
            adjacent = []
            for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                nx, ny = init_x + dx, init_y + dy
                if 0 <= nx < 4 and 0 <= ny < 4:
                    adjacent.append((nx, ny))
            # Determine obstacles (unmoved pieces' initial positions)
            obstacles = set()
            for p in move_pieces:
                if p not in moved and p != piece:
                    px, py = initial_pos[p]
                    obstacles.add((px, py))
            # Check if any adjacent position is reachable
            found = False
            for adj in adjacent:
                if bfs(current_empty, adj, obstacles):
                    current_empty = (init_x, init_y)
                    moved.add(piece)
                    found = True
                    break
            if not found:
                valid = False
                break
        if valid:
            print("Yes")
            return
    print("No")

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