一个街区（矩阵），R是闲置地区，B是建筑，G是路障。选择一个闲置地区R建立车站，使得车站到所有建筑的距离之和最短。注：只能向上、下、左、右走，可以穿过R和B，无法穿过G。
例：
RRRRR
RBGRR
RRGBR
RGBRR
RRRRR
RBGRR
RRGBR
RGBRR
RRRRR
答案：选择[1, 3]的R建立车站，到3个B的距离分别是1、3、4，总距离之和最短，为8。
刚刚面试的题目，只会暴力解法。求大神教一下有什么巧妙方法吗？
matrix = [['R','R','R','R','R'],['R','B','G','R','R'],['R','R','G','B','R'],['R','G','B','R','R'],['R','R','R','R','R']]
ans = [float("inf")]
best = [None, None]
def checkPath(matrix):
Buildings = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 'B':
Buildings.append([i, j])
def checkPathSum(matrix, i, j):
def checkPathNum(p1, p2, i, j, cur):
if p1 == i and p2 == j:
return cur
tmp = matrix[p1][p2]
matrix[p1][p2] = 'G'
A, B, C, D = float("inf"), float("inf"), float("inf"), float("inf")
if p1-1 >= 0 and matrix[p1-1][p2] != 'G':
A = checkPathNum(p1-1, p2, i, j, cur+1)
if p1+1 <= len(matrix)-1 and matrix[p1+1][p2] != 'G':
B = checkPathNum(p1+1, p2, i, j, cur+1)
if p2-1 >= 0 and matrix[p1][p2-1] != 'G':
C = checkPathNum(p1, p2-1, i, j, cur+1)
if p2+1 <= len(matrix[0])-1 and matrix[p1][p2+1] != 'G':
D = checkPathNum(p1, p2+1, i, j, cur+1)
matrix[p1][p2] = tmp
return min(A, B, C, D)
pathNum = 0
for build in Buildings:
pathNum += checkPathNum(build[0], build[1], i, j, 0)
if pathNum >= ans[0]:
return
if pathNum < ans[0]:
ans[0] = pathNum
best[0], best[1] = i, j
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 'R':
checkPathSum(matrix, i, j)
return ans[0], best
print(checkPath(matrix))
全部评论
(0) 回帖