Submission #1189334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189334		xumoyun_akromov1	Robots (APIO13_robots)	Pypy 3	0 / 100	135 ms	48776 KiB

robots

from collections import deque
from typing import List, Tuple

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

class Robot:
    def __init__(self, min_label, max_label, r, c):
        self.min_label = min_label
        self.max_label = max_label
        self.r = r
        self.c = c

    def __lt__(self, other):
        return (self.min_label, self.max_label, self.r, self.c) < (other.min_label, other.max_label, other.r, other.c)

    def __eq__(self, other):
        return (self.min_label, self.max_label, self.r, self.c) == (other.min_label, other.max_label, other.r, other.c)

    def __hash__(self):
        return hash((self.min_label, self.max_label, self.r, self.c))

def is_valid(r, c, H, W):
    return 0 <= r < H and 0 <= c < W

def get_grid_char(grid, r, c):
    if not is_valid(r, c, len(grid), len(grid[0])):
        return 'x'
    return grid[r][c]

def simulate_move(grid, r, c, d):
    H, W = len(grid), len(grid[0])
    ch = get_grid_char(grid, r, c)
    if ch == 'A':
        d = (d + 3) % 4
    elif ch == 'C':
        d = (d + 1) % 4
    while True:
        nr, nc = r + dr[d], c + dc[d]
        if not is_valid(nr, nc, H, W) or grid[nr][nc] == 'x':
            break
        r, c = nr, nc
        ch = grid[r][c]
        if ch == 'A':
            d = (d + 3) % 4
        elif ch == 'C':
            d = (d + 1) % 4
    return (r, c)

def merge_robots(robots):
    robots.sort()
    merged = True
    while merged:
        merged = False
        used = [False]*len(robots)
        new_robots = []
        for i in range(len(robots)):
            if used[i]: continue
            for j in range(i+1, len(robots)):
                if used[j]: continue
                a, b = robots[i], robots[j]
                if (a.r, a.c) == (b.r, b.c):
                    if a.max_label + 1 == b.min_label:
                        new_robots.append(Robot(a.min_label, b.max_label, a.r, a.c))
                        used[i] = used[j] = True
                        merged = True
                        break
                    elif b.max_label + 1 == a.min_label:
                        new_robots.append(Robot(b.min_label, a.max_label, a.r, a.c))
                        used[i] = used[j] = True
                        merged = True
                        break
            if not used[i]:
                new_robots.append(robots[i])
        robots = sorted(new_robots)
    return robots

def canonicalize(state):
    return tuple(sorted(state))

def solve(N, W, H, grid):
    robots = []
    for r in range(H):
        for c in range(W):
            if grid[r][c].isdigit():
                label = int(grid[r][c])
                robots.append(Robot(label, label, r, c))
    start = canonicalize(robots)

    q = deque()
    dist = {start: 0}
    q.append(start)

    while q:
        state = q.popleft()
        d = dist[state]

        if len(state) == 1 and state[0].min_label == 1 and state[0].max_label == N:
            return d

        for i, robot in enumerate(state):
            for dir in range(4):
                nr, nc = simulate_move(grid, robot.r, robot.c, dir)
                if (nr, nc) == (robot.r, robot.c):
                    continue
                moved = Robot(robot.min_label, robot.max_label, nr, nc)
                loc_map = {}
                for j, r2 in enumerate(state):
                    if i == j: continue
                    loc_map.setdefault((r2.r, r2.c), []).append(r2)
                loc_map.setdefault((nr, nc), []).append(moved)

                new_robots = []
                for robots_here in loc_map.values():
                    new_robots.extend(merge_robots(robots_here))
                new_state = canonicalize(new_robots)
                if new_state not in dist:
                    dist[new_state] = d + 1
                    q.append(new_state)
    return -1

# Foydalanish:
# N, W, H = 5, 4, 4
# grid = [
#     "1234",
#     "....",
#     "..AC",
#     "...."
# ]
# print(solve(N, W, H, grid))

Compilation message (stdout)

Compiling 'robots.py'...

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

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40