京东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

# print(dp1)
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])
全部评论
你这复杂度是n的3次方,应该能过50-60,拿bfs使用set维护,或者3维dp,3维dp最后一个纬度表示方向,同一个方向不用+1,不同方向+1,这题我直接看错了,刚开始没看到可以移动k,gg
2 回复 分享
发布于 2023-08-19 12:52 山西

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务