首页 > 试题广场 >

Shopee的办公室（二）

[编程题]Shopee的办公室（二）
  • 热度指数：9129 时间限制：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
算法知识视频讲解
添加回答
Python
王大涛头像 王大涛
感觉有点像递归或者爬梯子的样子，当前路径=坐标轴上左边的路径与坐标轴上下边的路径和。（即[i][j] = [i-1][j] + [i][j-1]） 
x , y , n = list(map(int , input().split()))
Boss = []
data = [[1]*(y+1) for _ in range(x+1)]
for i in range(n):
    Boss.append(list(map(int , input().split())))
for i in range(1 , x+1):
    for j in range(1 , y+1):
        if [i , j] in Boss:
            data[i][j] = 0
        else:
            data[i][j] = data[i-1][j] + data[i][j-1]
print(data[x][y])


发表于 2021-05-22 11:32:25 回复(0)
Python
sky游荡头像 sky游荡
玛德，开始推反了，想错了，一直过50%贼气。 
x,y,n = map(int,input().split())
dpc = [[1 for j in range(y+1)]for j in range(x+1)]
for _ in range(n):
    i,j = map(int,input().split())
    dpc[i][j] = 0
for i in range(1,x+1):
    for j in range(1,y+1):
        if dpc[i][j]!=0:
            dpc[i][j] = dpc[i-1][j]+dpc[i][j-1]
print(dpc[-1][-1])


发表于 2020-04-22 21:38:36 回复(0)
Python
大佬求带。。头像 大佬求带。。 
if __name__ == "__main__":
    x,y,n = list(map(int, input().split(" ")))
    dp = [[1 for i in range(x+1)] for j in range(y+1)]
    boss = []
    for i in range(n):
        bx,by = list(map(int, input().split(" ")))
        dp[bx][by]=0
    for i in range(1,x+1):
        for j in range(1,y+1):
            if dp[i][j]!= 0:
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
    print(dp[x][y])
为啥只能通过67%呢？？？
发表于 2019-08-03 16:35:33 回复(3)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

Shopee的办公室（二）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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