Problem Link - Siruseri Metro
Problem Statement
The city of Siruseri is impeccably planned. The city is divided into a rectangular array of cells with M rows and N columns. Each cell has a metro station. There is one train running left to right and back along each row, and one running top to bottom and back along each column. Each trains starts at some time T and goes back and forth along its route (a row or a column) forever.
Ordinary trains take two units of time to go from one station to the next. There are some fast trains that take only one unit of time to go from one station to the next. Finally, there are some slow trains that take three units of time to go from one station the next. You may assume that the halting time at any station is negligible.
Here is a description of a metro system with 3 rows and 4 columns :
S(1) F(2) O(2) F(4)
F(3) . . . .
S(2) . . . .
O(2) . . . .
The label at the beginning of each row/column indicates the type of train (F for fast, O for ordinary, S for slow) and its starting time. Thus, the train that travels along row 1 is a fast train and it starts at time 3. It starts at station (1, 1) and moves right, visiting the stations along this row at times 3,4,5 and 6 respectively. It then returns back visiting the stations from right to left at times 6,7,8 and 9. It again moves right now visiting the stations at times 9,10,11 and 12, and so on. Similarly, the train along column 3 is an ordinary train starting at time 2. So, starting at the station (3, 1), it visits the three stations on column 3 at times 2,4 and 6, returns back to the top of the column visiting them at times 6,8 and 10, and so on.
Given a starting station, the starting time and a destination station, your task is to determine the earliest time at which one can reach the destination using these trains.
Approach
The idea to solve the problem is to simulate the movement of trains and calculate the shortest travel time using Breadth-First Search (BFS)
. Each cell in the grid represents a metro station, and the BFS
explores neighboring cells to calculate the minimum time to reach them. For each train, its position at a given time is calculated using a periodic function that accounts for its back-and-forth movement. When visiting a neighboring cell, the earliest time at which the train can arrive is computed and updated. BFS
ensures that all possible paths are explored, and the minimum time to reach the destination is recorded. The logic revolves around systematically exploring all possible transitions, respecting train timings, and ensuring the shortest path is always prioritized.
Time Complexity
The time complexity is O(M \times N), as BFS
processes each cell in the grid at most once.
Space Complexity
The space complexity is O(M \times N), required for storing distances and the BFS
queue.