結果

問題 No.283 スライドパズルと魔方陣
ユーザー gew1fw
提出日時 2025-06-12 21:40:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,912 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 76,720 KB
最終ジャッジ日時 2025-06-12 21:44:23
合計ジャッジ時間 5,460 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def generate_magic_square(n):
    if n % 2 == 1:
        # Siamese method for odd n
        magic = [[0 for _ in range(n)] for _ in range(n)]
        row = 0
        col = n // 2
        for i in range(1, n*n + 1):
            magic[row][col] = i
            next_row = (row - 1) % n
            next_col = (col + 1) % n
            if magic[next_row][next_col] != 0:
                next_row = (row + 1) % n
                next_col = col
            row, col = next_row, next_col
        return magic
    else:
        # For even n, using a different method (e.g., Dürer's for n=4, generalized)
        magic = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(1, n*n + 1):
            row = (i - 1) // n
            col = (i - 1) % n
            if (row + col) % 2 == 0:
                magic[row][col] = i
            else:
                magic[row][col] = n*n + 1 - i
        return magic

def find_position(matrix, value):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == value:
                return (i, j)
    return None

def count_inversions(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                count += 1
    return count

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    grid = []
    for _ in range(N):
        row = list(map(int, input[ptr:ptr+N]))
        ptr += N
        grid.append(row)
    
    if N == 2:
        print("impossible")
        return
    
    # Generate the magic square
    magic = generate_magic_square(N)
    n_squared = N * N
    target_pos = find_position(magic, n_squared)
    if not target_pos:
        print("impossible")
        return
    target_x, target_y = target_pos
    
    # Check if initial grid's numbers (excluding 0) are permutation of magic's numbers (excluding n_squared)
    initial_nums = []
    for i in range(N):
        for j in range(N):
            val = grid[i][j]
            if val != 0:
                initial_nums.append(val)
    
    magic_nums = []
    for i in range(N):
        for j in range(N):
            val = magic[i][j]
            if val != n_squared:
                magic_nums.append(val)
    
    if sorted(initial_nums) != sorted(magic_nums):
        print("impossible")
        return
    
    # Extract the permutations for inversion count
    initial_perm = []
    for i in range(N):
        for j in range(N):
            val = grid[i][j]
            if val != 0:
                initial_perm.append(val)
    
    magic_perm = []
    for i in range(N):
        for j in range(N):
            val = magic[i][j]
            if val != n_squared:
                magic_perm.append(val)
    
    # Compute inversion counts
    inv_initial = count_inversions(initial_perm)
    inv_magic = count_inversions(magic_perm)
    
    # Find initial 0's position
    initial_zero = None
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 0:
                initial_zero = (i, j)
                break
        if initial_zero:
            break
    
    # Check solvability conditions
    if N % 2 == 1:
        # Odd N: same parity
        if (inv_initial % 2) != (inv_magic % 2):
            print("impossible")
            return
    else:
        # Even N: different parity and same color for empty tile
        if (inv_initial % 2) == (inv_magic % 2):
            print("impossible")
            return
        # Check if initial and target positions have the same parity
        if (initial_zero[0] + initial_zero[1]) % 2 != (target_x + target_y) % 2:
            print("impossible")
            return
    
    # If all checks passed, output the magic square
    print("possible")
    for row in magic:
        print(' '.join(map(str, row)))

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