Blocked lattice routes
HardOnline Assessment
Count the delivery routes through a city grid with closed intersections, modulo 1,000,000,007.
A city has intersections (r, c) for 0 <= r <= rows and 0 <= c <= cols, joined by streets between neighbouring intersections. A courier starts at (0, 0) and must reach (rows, cols). Every move goes to the next intersection south (r increases by 1) or east (c increases by 1); the courier never moves north or west.
On the way the courier must stop at the depot depot = [r, c], which always lies inside the grid. Some intersections listed in blocked are closed because of roadworks: a route may not pass through any of them, and this includes the start, the depot and the finish.
Two routes are different if they visit different sequences of intersections. A route passes through the depot exactly once, because the courier only ever moves forward.
Input: rows and cols, the size of the grid; depot, as [r, c]; and blocked, a list of [r, c] intersections (possibly with repeats, in no particular order).
Output: the number of valid routes from (0, 0) through the depot to (rows, cols), modulo 1_000_000_007. If there are none, return 0.
The grid can have hundreds of thousands of streets in each direction, so you cannot visit every intersection, but there are at most 300 closed ones.
Example 1
- Input:
- [2,2,[1,1],[]]
- Output:
- 4
- Explanation
- No intersection is closed. From (0, 0) to the depot (1, 1) there are 2 routes, and from (1, 1) to (2, 2) there are 2 more, so 2 * 2 = 4 delivery routes.
Example 2
- Input:
- [3,5,[1,2],[[2,4],[2,1],[0,2],[2,2]]]
- Output:
- 4
- Explanation
- Before the depot at (1, 2) there are 3 routes, but one runs through the closed (0, 2), leaving 2. After the depot, there are 10 routes to (3, 5); 4 pass through (2, 2) and 6 through (2, 4), but 2 pass through both, so 10 - 4 - 6 + 2 = 2 remain. Closed intersections that lie outside the stretch being driven, like (2, 1), do not matter. 2 * 2 = 4.
Example 3
- Input:
- [2,3,[1,1],[[1,1]]]
- Output:
- 0
- Explanation
- The depot (1, 1) is itself closed, so the courier cannot visit it and there are 0 routes.
Constraints
0 <= rows, colsandrows + cols <= 400,000depotis[r, c]with0 <= r <= rowsand0 <= c <= cols0 <= blocked.length <= 300; every blocked intersection[r, c]lies inside the grid, and the same intersection may be listed more than once