中级农民
- 积分
- 106
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2016-4-15
- 最后登录
- 1970-1-1
|
最後一輪:
我的解讀是在2D matrix中,找出一點P(i, j),使得該點距離最遠的設施之距離和最小
P(i, j) is not unique, 可能有複數個點值相等, 不過回傳一個大概就可以了
min( SUM( max( dist( P(i, j) - facility[f] ) ) ) )
設施:f = 1, 2, 3, 4,....etc
0: available
1: restaurant
2: Gym
3: ....
4: .....etc
-1: blocked
mat = [
[1,0,0,0,0,0,1,0],
[2,0,0,0,0,0,0,0],
[0,0,0,-1,0,0,2,0],
[0,0,4,-1,0,0,0,0],
[0,0,0,-1,0,0,0,0],
[0,0,0,-1,0,0,0,0],
[0,0,3,-1,0,0,0,0],
[0,0,0,0,0,0,3,0]
]
# output: dist = 20, position = [1 3]
"""
[
[0, 28, 24, 22, 24, 28, 0, 38],
[0, 26, 22, 20, 22, 26, 30, 34],
[30, 26, 24, 0, 24, 28, 0, 36],
[30, 26, 0, 0, 26, 30, 34, 38],
[32, 28, 30, 0, 28, 32, 36, 40],
[34, 30, 32, 0, 30, 34, 38, 42],
[36, 32, 0, 0, 32, 36, 40, 44],
[36, 32, 30, 29, 32, 36, 0, 48]]
"""
import collections
def minMaxDistance(mat):
m = len(mat)
n = len(mat[0])
shift = [-1, 0, 1, 0, -1]
buildingNum = 0
buildingFind = False
dist = [[0 for _ in range(n)] for _ in range(m)]
reach = [[0 for _ in range(n)] for _ in range(m)]
d = collections.defaultdict(list)
for i in range(m):
for j in range(n):
if mat[i][j] != 0 and mat[i][j] != -1:
d[mat[i][j]].append([i, j])
for key, val in d.items():
maxDist = [[0 for _ in range(n)] for _ in range(m)]
for i, j in val:
queue = collections.deque()
queue.append((i, j))
visited = [[0 for _ in range(n)] for _ in range(m)]
level = 1
while queue:
size = len(queue)
for _ in range(size):
r, c = queue.popleft()
for k in range(len(shift) - 1):
nr = r + shift[k]
nc = c + shift[k + 1]
if 0 <= nr < m and 0 <= nc < n and mat[nr][nc] == 0 and not visited[nr][nc]:
queue.append((nr, nc))
maxDist[nr][nc] = max(maxDist[nr][nc], level)
reach[nr][nc] += key
visited[nr][nc] = 1
level += 1
dist = [[dist[i][j] + maxDist[i][j] for j in range(n)] for i in range(m)]
reachBuildingSum = 0
for key, val in d.items():
for i, j in val:
reachBuildingSum += key
shortestDist = float("inf")
pos = [0, 0]
for i in range(m):
for j in range(n):
if mat[i][j] == 0 and reach[i][j] == reachBuildingSum:
if dist[i][j] <= shortestDist:
shortestDist = dist[i][j]
pos = [i, j]
return [shortestDist, pos]
print(minMaxDistance(mat))
补充内容 (2019-11-22 08:03):
time complexity: O(f * (traverse all elements in 2D) * (BFS)) = O(f * mn * mn) = O(f * m^2*n^2)
where f: category set of facilities |
|