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))
