百度9-3号笔试代码题

grid = [[1,2,2],
        [4,5,2],
        [7,8,2]]

n = len(grid)
table = {}

for i in range(n):
    for j in range(n):
        if (i,j) not in table:
            table[(i,j)] = []

        if 0 <= i+1 < n:
            table[(i,j)].append([(i+1,j),abs(grid[i+1][j] - grid[i][j])])
        if 0 <= i-1 < n:
            table[(i,j)].append([(i-1,j),abs(grid[i-1][j] - grid[i][j])])
        if 0 <= j+1 < n:
            table[(i,j)].append([(i,j+1),abs(grid[i][j+1] - grid[i][j])])
        if 0 <= j-1 < n:
            table[(i,j)].append([(i,j-1),abs(grid[i][j-1] - grid[i][j])])

visited = [[0 for _ in range(n)] for _ in range(n)]

dist = [[999 for _ in range(n)] for _ in range(n)]

dist[0][0] = 0

for _ in range(n*n):
    my_min = 1000
    pivot = (0,0)

    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                if dist[i][j] < my_min:
                    my_min = dist[i][j]
                    pivot = (i,j)

    idx,idy = pivot
    visited[idx][idy] = 1
    path = table[pivot]

    for m in range(len(path)):
        next_ptx,next_pty = path[m][0]
        next_dis = path[m][1]
        dist[next_ptx][next_pty] = min(dist[next_ptx][next_pty],dist[idx][idy] + next_dis)

print(dist)

#笔试题目#
全部评论

相关推荐

05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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