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.