lintcode 826电脑维修

 1 # 一个n * m矩阵代表一个电脑的阵列，给你一个list< Point >代表坏掉的电脑坐标。现在我们从(0,0)出发修电脑，要求：
 2 # 1.必须修完当前行所有坏掉的电脑才能走向下一行。
 3 # 2.如果要走向下一行，修理工必须先返回到这一行的最左端或者最右端。
 4 # 求最短的访问距离。
 5 #
 6 # 输入的矩阵大小为 n x m ，n <= 200，m <= 200。
 7 # 坏掉的机器 num <= 1000。
 8 # 修完最后一台电脑后，也需要返回最后一行的最左端或最右端。
 9 
10 # example：
11 # Input:
12 # n = 3
13 # m = 10
14 # list = [[0,0],[0,9],[1,7]]
15 # Output: 15
16 # Explanation:
17 # Starting from (0,0), fix 0, then go to (0,9) to fix 1 and go from (0,9) to next line (1,9), then go to (1,7) to fix 3, then go back to (1,9) and go to (2,9).
18 
19 
20 class Solution:
21     """
22     @param n: 行
23     @param m: 列
24     @param badcomputers: 坏电脑
25     @return: 答案
26     """
27 
28     def maintenance(self, n, m, badcomputers):
29         dp = [[0, 0] for i in range(n)]  # 每一行作为一个子问题，用该数组存储该行的左边解和右边解的步数
30         matrix = [[0 for i in range(m)] for j in range(n)]  # 初始化一个n*m的元素为0的矩阵
31         # 坏电脑矩阵元素设为1
32         for node in badcomputers:
33             matrix[node[0]][node[1]] = 1 # lintcode上badcomputers为Point类型，需要用node.x和node.y
34         for i in range(n):
35             most_right = -1  # 右边距
36             most_left = -1  # 左边距
37             for j in range(m):
38                 if matrix[i][j] != 0:
39                     most_right = max(most_right, j)
40                     most_left = max(most_left, m - 1 - j)
41             if i == 0:
42                 if most_right == -1:
43                     dp[0][0] = 0
44                     dp[0][1] = m - 1
45                 else:
46                     dp[0][0] = 2 * most_right
47                     dp[0][1] = m - 1
48                 continue
49             if most_right == -1:  # 如果该行没有坏电脑，直接进入下一行
50                 dp[i][0] = dp[i - 1][0] + 1
51                 dp[i][1] = dp[i - 1][1] + 1
52             else:  # 取当前行相对上一行的最优解
53                 dp[i][0] = min(dp[i - 1][0] + 2 * most_right,
54                                dp[i - 1][1] + m - 1) + 1
55                 dp[i][1] = min(dp[i - 1][1] + 2 * most_left,
56                                dp[i - 1][0] + m - 1) + 1
57         return min(dp[n - 1][0], dp[n - 1][1])
58 
59 
60 if __name__ == ‘__main__‘:
61     # n = 3
62     # m = 10
63     # list = [[0, 0], [0, 9], [1, 7]]
64     n = 3
65     m = 10
66     list = [[0, 3], [1, 7], [1, 2]]
67     solution = Solution()
68     res = solution.maintenance(n, m, list)
69     print(res)