from collections import deque
def parse_input():
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
w = int(data[1])
h = int(data[2])
grid = [list(data[i + 3]) for i in range(h)]
return n, w, h, grid
def get_initial_positions(grid):
positions = {}
for y, row in enumerate(grid):
for x, cell in enumerate(row):
if cell.isdigit():
positions[int(cell)] = (y, x)
return positions
def is_within_bounds(x, y, w, h):
return 0 <= x < w and 0 <= y < h
def move_robot(y, x, dy, dx, grid, w, h):
while is_within_bounds(x + dx, y + dy, w, h) and grid[y + dy][x + dx] != 'x':
y += dy
x += dx
if grid[y][x] == 'A':
dy, dx = -dx, dy
elif grid[y][x] == 'C':
dy, dx = dx, -dy
return y, x
def bfs(n, w, h, grid, positions):
initial_state = (tuple(sorted(positions.items())), 0)
queue = deque([initial_state])
visited = set([tuple(sorted(positions.items()))])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
while queue:
current_state, pushes = queue.popleft()
current_positions = dict(current_state)
# Check if all robots are merged
if len(current_positions) == 1 and 1 in current_positions:
return pushes
for robot in current_positions:
y, x = current_positions[robot]
for dy, dx in directions:
new_y, new_x = move_robot(y, x, dy, dx, grid, w, h)
new_positions = current_positions.copy()
new_positions[robot] = (new_y, new_x)
# Perform merging of robots on the same grid
merged_positions = {}
for label, (my, mx) in new_positions.items():
if (my, mx) not in merged_positions:
merged_positions[(my, mx)] = []
merged_positions[(my, mx)].append(label)
next_positions = {}
for pos, labels in merged_positions.items():
merged_label = (min(labels), max(labels))
next_positions[merged_label] = pos
next_state = tuple(sorted(next_positions.items()))
if next_state not in visited:
visited.add(next_state)
queue.append((next_state, pushes + 1))
return -1
def main():
n, w, h, grid = parse_input()
initial_positions = get_initial_positions(grid)
result = bfs(n, w, h, grid, initial_positions)
print(result)
if __name__ == "__main__":
main()
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1563 ms |
21296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1563 ms |
21296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1563 ms |
21296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1563 ms |
21296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
