# 虾皮笔试-机器人


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)