首页 > 试题广场 >

简单变向

[编程题]简单变向

热度指数：2321 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛准备在一个3行n列的跑道上跑步。一开始牛牛位于(1,1)。

当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：

1. 跑到第i行第j+1列
2. 跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
3. 跑到第i+1行第j+1列（如果i=3则不可以这么跑）。

跑道上有一些格子设置了路障(一个格子可能有多个路障)，牛牛不能跑到路障上。现在牛牛想知道，从(1,1)到(3,n)有多少条不同的路径？

为了防止答案过大，答案对1e9+7取模。

示例1

输入

4,1,[1],[2]

输出

说明

在第一行第二列的位置有一个障碍
牛牛有两种跑法：
1.  (1,1)->(2,2)->(2,3)->(3,4)
2.  (1,1)->(2,2)->(3,3)->(3,4)

备注:

，数据保证(1,1)和(3,n)上没有路障。
第一个参数n代表列数
第二个参数m代表路障个数
第三个参数和第四个参数x, y都包含m个元素，分别代表路障的行坐标和列坐标。
同一个格子可能有多个路障。

算法知识视频讲解

xqxls

发表于 2021-08-13 14:27:02

题意整理牛牛在一个3行n列的跑道上跑步。牛牛的下一步只能在原来的那一行，或者由相邻行跳转过来（不能跨行或者越界）。求牛牛从(1,1)到(3,n)有多少条不同的路径可走。方法一（记忆化递归） 1.解题思路递归终止条件：起点第1行第1列的位置肯定是可达的。递归如何推进：总共有1，2，3 展开全文

QSheng

发表于 2021-08-05 16:22:23

解题思路（参考爬楼梯的例子）： 1. 障碍物记录，用字典，方便查找 2. 障碍物在同一列超过3个，就返回0 3. 动态转移方程 dp[0][i] = 0 if "有障碍" else int((dp[0][i-1] + dp[1][i-1]) % b 展开全文

SandMonth

发表于 2021-09-14 21:02:33

简单变向牛牛准备在一个3行n列的跑道上跑步。一开始牛牛位于(1,1)。当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：跑到第i行第j+1列跑到第i-1行第j+1列（如果i=1则不可以这么跑）。跑到第i+1行第j+1列（如果i=3则不可以这么跑）。跑道上有一些格子设置了路障(一展开全文

球球了给孩子一个offer吧

发表于 2021-08-14 14:11:19

题目：矩阵大小为3xn，以(1,1)为起点可以向右走，右上对角线走，右下对角线走（不能出界），有些位置设置了路障，走不了，求出从(1,1)到(3,n)的路径数量方法一：记忆化递归可以用自顶向下的递归解决初始化路障数组，遇到路障直接返回0，为了避免重复计算，初始化记忆数组每个位置为0，用记忆数组记录展开全文