제출 #1147334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147334		aldo2902	Coin Collecting (JOI19_ho_t4)	Pypy 3	0 / 100	1101 ms	286584 KiB

joi2019_ho_t4

from collections import deque

def bfs(start, target):
    queue = deque([(start[0], start[1], 0)])  # (x, y, distancia)
    visited = set()
    visited.add((start[0], start[1]))

    while queue:
        x, y, dist = queue.popleft()
        if (x, y) == target:
            return dist
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, dist + 1))
    return float('inf')

def solve_coin_collecting(N, coin_positions):
    targets = [(x, y) for x in range(1, N + 1) for y in range(1, 3)]
    total_moves = 0
    used_targets = set()

    for coin in coin_positions:
        min_moves = float('inf')
        best_target = None

        for target in targets:
            if target not in used_targets:
                moves = bfs(coin, target)
                if moves < min_moves:
                    min_moves = moves
                    best_target = target

        total_moves += min_moves
        used_targets.add(best_target)

    return total_moves

import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
coin_positions = [(int(data[i * 2 + 1]), int(data[i * 2 + 2])) for i in range(2 * N)]

result = solve_coin_collecting(N, coin_positions)
print(result)

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'joi2019_ho_t4.py'...

=======
  adding: __main__.pyc (deflated 42%)

=======

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63