There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7. Example 1:Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0Output: 6
Question
There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7. Example 1:Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0Output: 6
Solution
This problem can be solved using dynamic programming. Here are the steps:
-
Initialize a 3D array dp of size (m, n, maxMove + 1) to store the number of paths for each cell at each move.
-
For each move from 1 to maxMove, iterate through each cell in the grid. For each cell, calculate the number of paths that move the ball out of the grid from this cell. This can be done by checking the four adjacent cells. If an adjacent cell is out of the grid, then there is one path out of the grid. If an adjacent cell is inside the grid, then the number of paths out of the grid from this cell is the number of paths at the adjacent cell at the previous move.
-
After calculating the number of paths for all cells at the current move, update the dp array for the next move.
-
After all moves, the number of paths to move the ball out of the grid from the start cell is the number of paths at the start cell at maxMove.
-
Since the answer can be very large, return it modulo 10^9 + 7.
Here is a Python solution:
def findPaths(m, n, maxMove, startRow, startColumn):
MOD = 10**9 + 7
dp = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for move in range(1, maxMove + 1):
for x in range(m):
for y in range(n):
for dx, dy in directions:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n:
dp[x][y][move] += 1
else:
dp[x][y][move] = (dp[x][y][move] + dp[nx][ny][move - 1]) % MOD
return dp[startRow][startColumn][maxMove] % MOD
In the example given, findPaths(2, 2, 2, 0, 0) returns 6.
Similar Questions
You are given an m x n matrix grid consisting of positive integers. You can move from a cell in the matrix to any other cell that is either to the bottom or to the right (not necessarily adjacent). The score of a move from a cell with the value c1 to a cell with the value c2 is c2 - c1.You can start at any cell, and you have to make at least one move.Return the maximum total score you can achieve. Example 1:Input: grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]Output: 9Explanation: We start at the cell (0, 1), and we perform the following moves:- Move from the cell (0, 1) to (2, 1) with a score of 7 - 5 = 2.- Move from the cell (2, 1) to (2, 2) with a score of 14 - 7 = 7.The total score is 2 + 7 = 9.Example 2:Input: grid = [[4,3,2],[3,2,1]]Output: -1Explanation: We start at the cell (0, 0), and we perform one move: (0, 0) to (0, 1). The score is 3 - 4 = -1. Constraints:m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1051 <= grid[i][j] <= 105
You are on a 22-dimensional grid, where you start at (0,0)(0,0).You are given a binary string 𝑆S of length 44 where:𝑆1S 1 refers to left direction;𝑆2S 2 refers to right direction;𝑆3S 3 refers to up direction;𝑆4S 4 refers to down direction.𝑆𝑖=1S i =1 denotes that you are allowed to make a move in the respective direction and vice-versa.Find the number of cells (𝑥,𝑦)(x,y) you can possibly visit which satisfy −10≤𝑥,𝑦≤10−10≤x,y≤10.Note that:You always include the cell (0,0)(0,0) in your answer.If you can visit (𝐴1,𝐵1)(A 1 ,B 1 ) and (𝐴2,𝐵2)(A 2 ,B 2 ) individually, but not both at the same time, you will still include both of them in your answer.Moves are defined as:A move in left direction is a move from cell (𝐴,𝐵)(A,B) to (𝐴−1,𝐵)(A−1,B).A move in right direction is a move from cell (𝐴,𝐵)(A,B) to (𝐴+1,𝐵)(A+1,B).A move in up direction is a move from cell (𝐴,𝐵)(A,B) to (𝐴,𝐵+1)(A,B+1).A move in down direction is a move from cell (𝐴,𝐵)(A,B) to (𝐴,𝐵−1)(A,B−1).Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of a binary string 𝑆S of length 44 - denoting the directions in which moves are allowed.Output FormatFor each test case, output on a new line, the number of cells you can visit as mentioned in statement.Constraints1≤𝑇≤151≤T≤15∣𝑆∣=4∣S∣=4𝑆𝑖∈{0,1}S i ∈{0,1}𝑆𝑖=1S i =1 for at least one 1≤𝑖≤41≤i≤4.Sample 1:InputOutput5001011000110111011111121121231441Explanation:Test case 11: The only allowed direction is up. Thus, you can only visit cells (0,0),(0,1),(0,2),…,(0,10)(0,0),(0,1),(0,2),…,(0,10); which are a total of 1111 cells.Test case 22: The allowed directions are left and right. Thus, you can visit cells (−10,0),(−9,0),…,(0,0),…,(9,0),(10,0)(−10,0),(−9,0),…,(0,0),…,(9,0),(10,0), which are a total of 2121 cells.Test case 33: The allowed directions are right and up. You can visit all cells (𝑥,𝑦)(x,y) such that 𝑥≥0x≥0 and 𝑦≥0y≥0, which are a total of 121121 cells.
You are given four integers sx, sy, fx, fy, and a non-negative integer t.In an infinite 2D grid, you start at the cell (sx, sy). Each second, you must move to any of its adjacent cells.Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise.A cell's adjacent cells are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.
Given an integer ‘N’, you need to make the maximum possible number of moves where each move consists of choosing a positive integer ‘X’ > 1, such that ‘N’ is divisible by ‘X’ and replacing ‘N’ with ‘N/X’.When ‘N’ becomes equal to 1 and there are no more possible valid moves. You need to stop and your score is equal to the number of moves made.Given ‘N’ is of the form a! / b! ( i.e. factorial of ‘a’ divided by factorial of ‘b’) for some positive integer ‘a’ and ‘b’ (a ≥ b).You need to find and return the maximum possible score you can achieve.
Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (r
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.