576. Out of Boundary Paths

Problem

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 four 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 = 0
Output: 6

Example 2:

Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output: 12

Constraints:

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow <= m
• 0 <= startColumn <= n

Problem Summary

Given an m × n grid and a ball. The ball's starting coordinates are (i,j) . You can move the ball into an adjacent cell, or move it up, down, left, or right so that it crosses the grid boundary. However, you can move at most N times. Find the number of paths that can move the ball out of the boundary. The answer may be very large, so return the value of result mod 109 + 7.

Solution Approach

• A purely brute-force approach is to traverse one step in each direction of the ball until the number of moves is exhausted. With this brute-force search, the solution space is 4^n. The optimization idea is to add memoization. Use a three-dimensional array to record the position coordinates and the number of steps, corresponding to the number of paths out of the boundary. With memoization added, the DFS solution runtime beats 100%.

Code

package leetcode

var dir = [][]int{
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
}

func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
	visited := make([][][]int, m)
	for i := range visited {
		visited[i] = make([][]int, n)
		for j := range visited[i] {
			visited[i][j] = make([]int, maxMove+1)
			for l := range visited[i][j] {
				visited[i][j][l] = -1
			}
		}
	}
	return dfs(startRow, startColumn, maxMove, m, n, visited)
}

func dfs(x, y, maxMove, m, n int, visited [][][]int) int {
	if x < 0 || x >= m || y < 0 || y >= n {
		return 1
	}
	if maxMove == 0 {
		visited[x][y][maxMove] = 0
		return 0
	}
	if visited[x][y][maxMove] >= 0 {
		return visited[x][y][maxMove]
	}
	res := 0
	for i := 0; i < 4; i++ {
		nx := x + dir[i][0]
		ny := y + dir[i][1]
		res += (dfs(nx, ny, maxMove-1, m, n, visited) % 1000000007)
	}
	visited[x][y][maxMove] = res % 1000000007
	return visited[x][y][maxMove]
}