An ant is placed on a width x height
grid.
(0, 0)
, and the bottom-right corner is represented as (width - 1, height - 1)
.(x, y)
within the grid. Each second, it can only move one unit left, right, up, or down.(0, i)
, (width - 1, i)
, (i, 0)
, or (i, height - 1)
for any valid i
.Given the grid dimensions (width
and height
), the starting point (x, y)
, and a list of integer steps steps
, determine after how many seconds the ant will first be at the boundary.
0
.(x, y)
is already on the boundary. If so, return 0
.from collections import deque
def time_to_boundary(width, height, x, y, steps):
# Check if already at the boundary
if x == 0 or x == width - 1 or y == 0 or y == height - 1:
return 0
# Possible directions (left, right, up, down)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Initialize the queue with the starting position and time = 0
queue = deque([(x, y, 0)])
visited = set((x, y))
while queue:
cx, cy, time = queue.popleft()
if time > steps:
break
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in visited:
# Check if the next position is a boundary position
if nx == 0 or nx == width - 1 or ny == 0 or ny == height - 1:
return time + 1
# Mark the new position as visited and add to the queue
visited.add((nx, ny))
queue.append((nx, ny, time + 1))
return steps
# Example Usage:
width = 5
height = 5
x = 2
y = 2
steps = 10
print(time_to_boundary(width, height, x, y, steps)) # Expected output should be the time when it hits the boundary based on steps allowed
This algorithm efficiently simulates the ant’s movement and determines the first time it hits the boundary.
Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?