Problem Link - Highway Bypass
Problem Statement
Due to resurfacing work, all north-south traffic on the highway is being diverted through the town of Siruseri. Siruseri is a modern, planned town and the section of roads used for the diversion forms a rectangular grid where all cars enter at the top-left intersection (north- west) and leave at the bottom-right intersection (south-east). All roads within the grid are one-way, allowing traffic to move north to south (up-down) and west to east (left-right) only.
The town authorities are concerned about highway drivers overspeeding through the town. To slow them down, they have made a rule that no car may travel more than d consecutive road segments in the same direction without turning. (Closed-circuit TV cameras have been installed to enforce this rule.)
Of course, there is also repair work going on within the town, so some intersections are blocked and cars cannot pass through these.
You are given the layout of the rectangular grid of roads within Siruseri and the constraint on how many consecutive road segments you may travel in the same direction. Your task is to compute the total number of paths from the entry (top-left) to the exit (bottom-right).
For instance, suppose there are 3 rows and 4 columns of intersections, numbered from (1,1) at the top-left to (3,4) at the bottom-right, as shown on the right. Intersection (2,1) in the second row, first column is blocked, and no car may travel more than 2 consecutive road seg- ments in the same direction.
Here, (1,1) → (1,2) → (2,2) → (3,2) → (3,3) → (3,4) is a valid path from (1,1) to (3,4), but (1,1) → (1,2) → (1,3) → (1,4) → (2,4) → (3,4) is not, because this involves 3 consecutive road segments from left to right. The path (1, 1) → (2, 1) → (2, 2) → (2, 3) → (3, 3) → (3, 4) is ruled out because it goes through a blocked intersection. In this example, you can check that the total number of valid paths is 5.
Approach
To solve this problem, we use dynamic programming to keep track of all the ways cars can move from the top-left to the bottom-right intersection, considering the constraints. We maintain a 3D array ways, where each cell stores the number of ways to reach that intersection. The first dimension represents the row, the second the column, and the third stores two values: the number of ways moving left (0) and up (1).
We initialize the entry point as having 1 way, both left and up, since we are starting from there. Then for each cell in the grid, we check the possible moves based on the previous cells in the grid, considering the constraints on how many consecutive road segments can be traveled in the same direction. For leftward movement, we look back at previous intersections in the same row, considering the maximum distance allowed. Similarly, for upward movement, we check previous intersections in the same column.
We ensure that blocked intersections are handled by skipping those cells during the update of the ways array. At the end, the number of ways to reach the bottom-right corner is the sum of the number of ways to reach it from the left and from the top.
Time Complexity
O(n \times m \times d), where n is rows, m is columns, and d is the max consecutive road segments allowed.
Space Complexity
O(n \times m), for storing paths for each intersection.