結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    target = []
    for _ in range(4):
        row = list(map(int, sys.stdin.readline().split()))
        target.append(row)
    
    initial = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 0]
    ]
    
    if target == initial:
        print("Yes")
        return
    
    target_zero = None
    for i in range(4):
        for j in range(4):
            if target[i][j] == 0:
                target_zero = (i, j)
                break
        if target_zero is not None:
            break
    
    initial_zero = (3, 3)
    
    visited = {}
    queue = deque()
    queue.append( (initial_zero[0], initial_zero[1], 0, initial) )
    visited_key = (initial_zero[0], initial_zero[1], 0)
    visited[visited_key] = True
    
    directions = [ (-1, 0), (1, 0), (0, -1), (0, 1) ]
    
    while queue:
        x, y, mask, board = queue.popleft()
        
        if (x, y) == target_zero:
            if board == target:
                print("Yes")
                return
        
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < 4 and 0 <= ny < 4:
                tile = board[nx][ny]
                if tile == 0:
                    continue
                if (tile >> (tile - 1)) & mask:
                    continue
                
                new_mask = mask | (1 << (tile - 1))
                new_board = [row.copy() for row in board]
                new_board[x][y] = tile
                new_board[nx][ny] = 0
                
                visited_key = (nx, ny, new_mask)
                if visited_key not in visited:
                    visited[visited_key] = True
                    queue.append( (nx, ny, new_mask, new_board) )
    
    print("No")

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