576. 出界的路径数

短命女 2022-10-10 01:50 14阅读 0赞

> 给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ，你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动 N 次。找出可以将球移出边界的路径数量。答案可能非常大，返回 结果 mod 109 + 7 的值。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
        int MOD=(int)1e9+7;
        Long memo[][][];
        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            /**
            记忆化dfs
             */
             memo=new Long[m][n][maxMove+1];
            return (int)dfs(m,n,maxMove,startRow,startColumn);
             
        }
    
        public long dfs(int m, int n, int maxMove, int i, int j){
            if(i<0||j<0||i>=m||j>=n){
                return 1;
            }
            if(maxMove==0){
                return 0;
            }
            if(memo[i][j][maxMove]!=null){
                return memo[i][j][maxMove];
            }
            long  res=0;
            res=(res+dfs(m,n,maxMove-1,i-1,j))%MOD;
            res=(res+dfs(m,n,maxMove-1,i+1,j))%MOD;
            res=(res+dfs(m,n,maxMove-1,i,j-1))%MOD;
            res=(res+dfs(m,n,maxMove-1,i,j+1))%MOD;
            memo[i][j][maxMove]=res;
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/ef5c53ca881e45b7bc4d0e66fa5a9751.png

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关基本路径法之求基本路径数

![format_png][] 求上图的基本路径 > 基本路径条数的三种方法： > > 1）控制流图的区域数 > 2）边数-节点+2 > 3）判定节点数+1

小灰灰/ 2023年07月25日 06:15/ 0 赞/ 40 阅读

相关 LeetCode 576. 出界的路径数

解题思路这题其实用逆向思维更简单。dp\[i\]\[j\]\[k\]表示从外界走k步能到达(i,j)。状态转移很简单，无非就是dp\[i\]\[j\]\[k\]+

ゝ一世哀愁。/ 2023年07月05日 13:09/ 0 赞/ 17 阅读

相关 Leetcode 576. 出界的路径数

Leetcode 576. 出界的路径数 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn

刺骨的言语ヽ痛彻心扉/ 2023年02月11日 07:16/ 0 赞/ 114 阅读

相关 576. 出界的路径数

> 给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ，你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动

短命女/ 2022年10月10日 01:50/ 0 赞/ 15 阅读

相关 576-二分搜索算法(折半查找)

如果数据序列是无序的，我们采用的是线性搜索，时间复杂度是O(n） ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_s

电玩女神/ 2022年09月11日 14:21/ 0 赞/ 208 阅读

相关 576 出界的路径数（动态规划-递推）

1. 问题描述：给你一个大小为 m x n 的网格和一个球。球的起始坐标为 \[startRow, startColumn\] 。你可以将球移到在四个方向上相邻的单元格内（

左手的ㄟ右手/ 2022年08月31日 11:10/ 0 赞/ 188 阅读

相关 leetcode 576. Out of Boundary Paths | 576. 出界的路径数（暴力递归-＞傻缓存-＞dp）

题目 [https://leetcode.com/problems/out-of-boundary-paths/][https_leetcode.com_problems

偏执的太偏执、/ 2022年08月28日 08:56/ 0 赞/ 161 阅读

相关 leetcode 576. Out of Boundary Paths K步内出界的次数之和 + DP动态规划

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you c

约定不等于承诺〃/ 2022年06月03日 04:39/ 0 赞/ 149 阅读

相关 echarts中tooltips，鼠标移入提示框出界问题

1.confine:true 2.tooltip: \{ position: function (pos, params, el, elRect,

小咪咪/ 2022年03月20日 06:20/ 0 赞/ 909 阅读

相关 576. Out of Boundary Paths

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you c

Love The Way You Lie/ 2022年01月12日 10:53/ 0 赞/ 184 阅读