結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    # Read the target grid
    target_grid = []
    for _ in range(4):
        row = list(map(int, sys.stdin.readline().split()))
        target_grid.append(row)
    
    # Determine the initial positions of each tile
    initial_pos = {}
    for i in range(4):
        for j in range(4):
            if i == 3 and j == 3:
                initial_pos[0] = (i+1, j+1)
            else:
                tile = 1 + i*4 + j
                initial_pos[tile] = (i+1, j+1)
    
    # Determine the target positions of each tile
    target_pos = {}
    for i in range(4):
        for j in range(4):
            tile = target_grid[i][j]
            target_pos[tile] = (i+1, j+1)
    
    # Determine the set S of tiles that need to be moved
    S = set()
    for tile in range(1, 16):
        if initial_pos[tile] != target_pos[tile]:
            S.add(tile)
    
    # Target empty position
    T = target_pos[0]
    
    # If no tiles need to be moved, output Yes
    if not S:
        print("Yes")
        return
    
    # Directions for empty space movement (up, down, left, right)
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    # BFS initialization
    # Each state is (empty_i, empty_j, frozenset(remaining_tiles))
    initial_state = (4,4, frozenset(S))
    visited = set()
    visited.add(initial_state)
    queue = deque()
    queue.append(initial_state)
    
    while queue:
        current = queue.popleft()
        empty_i, empty_j, remaining = current
        
        # Check if we've reached the target state
        if (empty_i, empty_j) == T and len(remaining) == 0:
            print("Yes")
            return
        
        # Explore all possible moves
        for di, dj in directions:
            ni = empty_i + di
            nj = empty_j + dj
            if 1 <= ni <= 4 and 1 <= nj <= 4:
                # Determine the tile that would be moved into the empty space
                tile = target_grid[ni-1][nj-1] if (ni, nj) in [(empty_i + di, empty_j + dj)] else None
                # Wait, no. The initial grid of the target is not relevant here.
                # Instead, the tile is the one at (ni, nj) in the initial grid.
                # So, get the tile's position in the initial grid.
                for t in initial_pos:
                    if initial_pos[t] == (ni, nj):
                        tile = t
                        break
                else:
                    tile = None
                if tile is None:
                    continue
                
                # Check if the tile is in the remaining set
                if tile not in remaining:
                    continue
                
                # Check if the tile's target position is the current empty position
                if target_pos[tile] != (empty_i, empty_j):
                    continue
                
                # Create the new remaining set
                new_remaining = set(remaining)
                new_remaining.remove(tile)
                new_remaining_frozen = frozenset(new_remaining)
                
                # Check if this new state has been visited
                new_state = (ni, nj, new_remaining_frozen)
                if new_state not in visited:
                    visited.add(new_state)
                    queue.append(new_state)
    
    # If BFS completes without finding a solution
    print("No")

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