884. Off the Edge
A small robot ball sits on cell (startRow, startCol) of an m x n board, with rows numbered from 0 to m-1 and columns from 0 to n-1. In each push the ball rolls exactly one cell up, down, left or right. It may roll off the board.
Count the push sequences of length at most maxMove that make the ball leave the board for the first time on their last push (the ball stops being pushed once it is off). Two sequences are different if some push direction differs. Return the count modulo 1000000007.
Example 1
- Input:
- m = 2n = 2maxMove = 2startRow = 0startCol = 0
- Output:
- 6
- Explanation:
On a 2x2 board starting at (0,0) with at most 2 pushes there are 6 push sequences that send the ball off the board (2 immediately, then 4 more after a push onto a neighbouring cell).
Example 2
- Input:
- m = 1n = 3maxMove = 3startRow = 0startCol = 1
- Output:
- 12
- Explanation:
Middle of a 1x3 row: up or down leaves at once (2 ways); left or right reaches an edge cell, from which up, down or outward leaves on push 2 (3 exits for each of 2 paths = 6), while moving back inward returns to the middle and gives 2 more exits on push 3 for each of 2 paths (4). Total 2 + 6 + 4 = 12.
Example 3
- Input:
- m = 3n = 3maxMove = 0startRow = 1startCol = 1
- Output:
- 0
- Explanation:
With zero pushes the ball cannot leave, so the answer is 0.
Constraints
- 1 ≤ m, n ≤ 50
- 0 ≤ maxMove ≤ 50
- 0 ≤ startRow < m, 0 ≤ startCol < n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(maxMove * m * n)
- Space
- O(m * n)