京东8.19笔试

A了两道,最后一道卡住了。

最后想出来的时候已经没时间了。

不知道下面这个方法对不对:有大佬帮忙看一下吗?

题目:皇后走棋盘,一次可以向右、向下、向右下走,棋盘有障碍物。求从左上角到右下角的最少步数。

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(input()))

dp = [[float("inf")] * m for _ in range(n)]
if board[0][0] == ".":
    dp[0][0] = 0

for i in range(n):
    for j in range(m):
        if board[i][j] == "." and dp[i][j] != float("inf"):
            k = 1
			# 往右走
            while j+k < m and board[i][j+k] == ".":
                dp[i][j+k] = min(dp[i][j+k], dp[i][j]+1)
                k += 1
            k = 1
			# 往下走
            while i+k < n and board[i+k][j] == ".":
                dp[i+k][j] = min(dp[i+k][j], dp[i][j]+1)
                k += 1
            k = 1
			# 往右下走
            while i+k < n and j+k < m and board[i+k][j+k] == ".":
                dp[i+k][j+k] = min(dp[i+k][j+k], dp[i][j]+1)
                k += 1

print(-1) if dp[n-1][m-1] == float("inf") else print(dp[n-1][m - 1])

全部评论
动态规划,dp数组保存走到棋盘每一个格子最少的步数,由于可以向右,向下,向右下,那么状态转移方程就是min(左上➕1,左➕1,上➕1),被障碍物阻塞无法到达的点用0表示。所以dp数组一开始全初始化成0就行了。
1 回复 分享
发布于 2023-08-19 14:23 黑龙江
应该是三维dp吧,你只定义两维dp应该不对吧
点赞 回复 分享
发布于 2023-08-19 15:05 安徽
我用C++超时了,a了40%
点赞 回复 分享
发布于 2023-08-19 15:38 浙江
京东笔试题型是什么样的啊,还有选择题吗
点赞 回复 分享
发布于 2023-08-20 20:09 江苏
这题需要三维dp,还有一维来记录有没有换方向
点赞 回复 分享
发布于 2023-08-22 13:27 广东
兄弟,试试光伏电池行业~
点赞 回复 分享
发布于 2023-09-21 07:31 浙江

相关推荐

01-24 04:44
门头沟学院 Java
数学转码崽:项目感觉有点简单,再加上学历不是92的话,大厂实习很难过筛吧,即使给几个面试,感觉也通过不了,还是放低预期,先去中厂沉淀吧,暑期实习可以试着冲大厂,如果非大厂不去的话,不如去考研,双非学历真的硬伤
点赞 评论 收藏
分享
真是做吐了🤮
投递美团等公司10个岗位 >
点赞 评论 收藏
分享
评论
2
4
分享

创作者周榜

更多
牛客网
牛客企业服务