[leetcode] 576. Out of Boundary Paths

[leetcode] 576. Out of Boundary Paths

Description

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1: Input:

m = 2, n = 2, N = 2, i = 0, j = 0

Output:

6

Explanation:

Example 2:

Input:

m = 1, n = 3, N = 3, i = 0, j = 1

Output:

12

Explanation:

Note:

Once you move the ball out of boundary, you cannot move it back.The length and height of the grid is in range [1,50].N is in range [0,50].

分析

题目的意思是：有一个小球在网格里，你最多只能移动n次，问移出界的路径有多少。

dp[k][i][j]表示总共走k步，从(i,j)位置走出边界的总路径数那么我们来找递推式，对于dp[k][i][j]，走k步出边界的总路径数等于其周围四个位置的走k-1步出边界的总路径数之和，如果周围某个位置已经出边界了，那么就直接加上1，否则就在dp数组中找出该值，这样整个更新下来，我们就能得出每一个位置走任意步数的出界路径数了，最后只要返回dp[N][i][j]就是所求结果了。

代码

class Solution {public: int findPaths(int m, int n, int N, int i, int j) { vector>> dp(N+1,vector>(m,vector(n,0))); for(int k=1;k<=N;k++){ for(int x=0;x

参考文献

​​[LeetCode] Out of Boundary Paths 出界的路径​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。