首页 > 2021-7-5【虾皮笔试】:机器人
头像
__wsx__
编辑于 2021-07-05 18:06
+ 关注

2021-7-5【虾皮笔试】:机器人

2021-7-5【虾皮笔试】:
机器人题目:
我的思路:用dfs找出所有能到达终点的路径,再用前缀和数组求出每条路径的触底体力值minH(也就是从路径头走到路径尾会出现的最低体力值),最后求出所有路径触底体力值的最大值,如果最大值大于0,直接返回1;否则返回触底体力值-minH+1.
# 虾皮笔试-机器人


class Solution:
    def minimumInitHealth(self, rooms, startPoint, endPoint):
        col_total = len(rooms[0])
        row_total = len(rooms)
        rooms_total = col_total * row_total
        # 记录访问过的
        visited = [[False for _ in range(col_total)] for _ in range(row_total)]
        # res记录路径
        res = []
        def dfs(rooms, row, col, path, visited, res):
            # stop condition
            if (row == endPoint[0] and col == endPoint[1])&nbs***bsp;len(path) == rooms_total:
                if row == endPoint[0] and col == endPoint[1]:
                    temp = path[:]
                    temp.append(rooms[row][col])
                    res.append(temp)
                return
            # bound
            if row >= row_total&nbs***bsp;row < 0&nbs***bsp;col >= col_total&nbs***bsp;col < 0&nbs***bsp;visited[row][col]:
                return
            # 回溯
            visited[row][col] = True
            path.append(rooms[row][col])
            dfs(rooms, row + 1, col, path, visited, res)
            dfs(rooms, row - 1, col, path, visited, res)
            dfs(rooms, row, col + 1, path, visited, res)
            dfs(rooms, row, col - 1, path, visited, res)
            path.pop()
            visited[row][col] = False

        dfs(rooms, startPoint[0], startPoint[1], [], visited, res)
        print('所有路径:', res)
        minH = []
        # 求出所有路径体力的前缀和
        for path in res:
            sum_ = [0]
            for value in path:
                sum_.append(sum_[-1]+value)
            minH.append(min(sum_))
        # 找出最大的触底体力
        if max(minH) < 0:
            return -max(minH)+1
        else:
            return 1


if __name__ == '__main__':
    s = Solution()
    # 测试用例
    rooms1 = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
    rooms3 = [[-2, -1, 1], [-5, 1, -10], [3, 1, -1]]
    rooms2 = [[2, 3, 3], [5, 10, 1], [10, 30, 5]]
    start = [0, 0]
    end = [2, 2]
    res = s.minimumInitHealth(rooms3, start, end)
    print(res)


程序还有很多可以优化的地方,欢迎批评指正。
楼主因为忘记考虑路径和大于0的情况才过了60。。发现的时候已经晚了。。。。

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐