一流学科建设专题网站,石家庄外贸网站建设,班级优化大师官方免费下载,wordpress 汽车 模板文章目录1. 题目2. 解题1. 题目
给定一个 m n 的网格和一个球。 球的起始坐标为 (i,j) #xff0c;你可以将球移到相邻的单元格内#xff0c;或者往上、下、左、右四个方向上移动使球穿过网格边界。 但是#xff0c;你最多可以移动 N 次。 找出可以将球移出边界的路径数量…
文章目录1. 题目2. 解题1. 题目
给定一个 m × n 的网格和一个球。 球的起始坐标为 (i,j) 你可以将球移到相邻的单元格内或者往上、下、左、右四个方向上移动使球穿过网格边界。 但是你最多可以移动 N 次。 找出可以将球移出边界的路径数量。 答案可能非常大返回 结果 mod 10^9 7 的值。
示例 1
输入: m 2, n 2, N 2, i 0, j 0
输出: 6示例 2
输入: m 1, n 3, N 3, i 0, j 1
输出: 12说明:
球一旦出界就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。来源力扣LeetCode 链接https://leetcode-cn.com/problems/out-of-boundary-paths 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 552. 学生出勤记录 II动态规划 LeetCode 688. “马”在棋盘上的概率DP LeetCode 935. 骑士拨号器动态规划 LeetCode 1220. 统计元音字母序列的数目DP
从外圈开始向内走dp[x][y][t] 表示在 x,y 处剩余 t 步时的方案数
class Solution {
public:int findPaths(int m, int n, int N, int i, int j) {if(N 0)return 0;vectorvectorvectorint dp(m,vectorvectorint(n, vectorint(N1, 0)));// dp[x][y][t] 表示在 x,y 处剩余t步时的方案数int x, y, ans 0, mod 1e97;for(y 0; y n; y){ //从边界往里面走初始化dp[0][y][N-1] 1;dp[m-1][y][N-1] 1;}for(x 0; x m; x){ //从边界往里面走初始化dp[x][0][N-1] 1;dp[x][n-1][N-1] 1;}ans (ansdp[i][j][N-1])%mod;//第一步走完int t N-1;while(t){vectorvectorvectorint temp(m,vectorvectorint(n, vectorint(N1, 0)));for(x 0; x m; x){for(y 0; y n; y){temp[x][y][t-1] (temp[x][y][t-1] (x 0 ? dp[x-1][y][t] : 0))%mod;temp[x][y][t-1] (temp[x][y][t-1] (y 0 ? dp[x][y-1][t] : 0))%mod;temp[x][y][t-1] (temp[x][y][t-1] (x m-1 ? dp[x1][y][t] : 0))%mod;temp[x][y][t-1] (temp[x][y][t-1] (y n-1 ? dp[x][y1][t] : 0))%mod;}//四个方向转移}ans (anstemp[i][j][t-1])%mod;//累加t--;dp temp;}return ans;}
};228 ms 104.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
