首页 > 试题广场 >

Shopee的办公室（二）

[编程题]Shopee的办公室（二）
  • 热度指数：9150 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
shopee的办公室非常大，小虾同学的位置坐落在右上角，而大门却在左下角，可以把所有位置抽象为一个网格（门口的坐标为0，0），小虾同学很聪明，每次只向上，或者向右走，因为这样最容易接近目的地，但是小虾同学不想让自己的boss们看到自己经常在他们面前出没，或者迟到被发现。他决定研究一下如果他不通过boss们的位置，他可以有多少种走法？


输入描述:
第一行 x,y,n (0<x<=30, 0<y<=30, 0<=n<= 20) 表示x,y小虾的座位坐标,n 表示boss的数量（ n <= 20）

接下来有n行, 表示boss们的坐标(0<xi<= x, 0<yi<=y，不会和小虾位置重合)

x1, y1

x2, y2

……

xn, yn


输出描述:
输出小虾有多少种走法
示例1

输入

3 3 2
1 1
2 2

输出

4
算法知识视频讲解
开通博客
头像 摆烂了的安迪很喜欢溜溜球
发表于 2022-06-15 19:51:10
本题以动态规划考虑求解 小虾同学只能从两个方向走，即他在每一个坐标的走法是他在该位置前两个方向上坐标走法的和（动态规划分解子问题）。 具体用公式表示为 #状态转移方程 dp[i][j]=dp[i][j-1]+dp[i-1][j] 不能通过boss的位置，所以经过boss位置时，dp数组定义为0 具 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-28 16:41:32
解题思路 这是一道典型的网格路径动态规划问题： 从左上角 出发，每次只能向右或向上移动 需要避开boss所在的位置 求到达右上角 的所有可能路径数 动态规划思路： 创建 数组， 表示到达位置 的路径数 如果当前位置有boss，则 否则 初始条件： 代码 #include < 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 想想何卓远会怎么做
发表于 2022-08-18 00:18:46
使用了 dfs bfs 都不行，看答案，才发现需要使用动态规划。。。 太坑了 package main import "fmt" func main() { x, y := 0, 0 n :=&nb 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 动态规划 虾皮信息 2019 数学 Java工程师
来自：Shopee 2019...
上传者：小小
难度：
53条回答 17848浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Shopee的办公室（二）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号