Massive Algorithms: [Google] Shortest Manhattan Distance

[Google] Shortest Manhattan Distance - Shuatiblog.com

给一个 n*m 的房间，房间里存在各种可能的墙，房间的格子里已经放了 e 个器材，要求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.

对 e个设备 BFS, 求每个设备到每个可以放新器材的点的距离，然后叠加。
最后O（n2）一遍找最小值。复杂度O（e*n2）

As for whether we choose to check each equipment position, or check each vacant position, it’s decided by how many equipment is there. If very little equipments (e is small), then this solution should work.

However, what is there is obstacles in the matrix?

We have to use BFS then. It took more space usage, but the time complexity should be same.

public void findCenter(int[][] input, int numberOfEquip) {
    int m = input.length;
    int n = input[0].length;

    // there's gonna be m * n positions
    // we gonna cumulate (numberOfEquip) distances for each position
    int[] dis = new int[m * n];

    // from the input map, find Equipments
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] == 1) {
                // 1 represents equipment
                // when found, add the distance to every position
                cumulateDistance(i, j, dis, m, n);
            }
        }
    }

    // find the smallest cumulated distance from dis[].
    int sIndex = 0;
    int smallest = dis[0];
    for (int i = 0; i < m * n; i++) {
        if (dis[i] < smallest) {
            smallest = dis[i];
            sIndex = i;
        }
    }

    // index sIndex is the final answer
    System.out.println("Answer: " + (sIndex / n) + " " + (sIndex % n));
}

private void cumulateDistance(int x, int y, int[] dis, int m, int n) {
    for (int i = 0; i < m * n; i++) {
        int a = i / n;
        int b = i % n;
        dis[i] += Math.abs(a - x) + Math.abs(b - y);
    }
}

http://www.mitbbs.com/article_t/JobHunting/33054861.html
http://www.meetqun.com/thread-10926-1-1.html
用O(n * m * e) 可以做，思路就是从每个器材点出发，求该器材点到每个可以放置位置的距离，然后把距离求和。就形成了一个n * m的距离矩阵，找距离矩阵中的最小值，返回该点坐标。

def get_location(self, room):3 C+ M: r m6 t: d( P! |& g
'''
time: O(n * m * k) k is num of equipments
space: O(k)
'''
m, n = len(room), len(room[0])& K2 | X4 r9 D4 \* N! Y
equipments = set()# H. A) l' D" x) c! S
# find all equipments in the room
for i in xrange(m):! L4 x/ Q4 E- |5 {
for j in xrange(n):
if room【i】[j] == 0:8 c7 R& G: v/ L/ g( f: c6 b
equipments.add((i, j))7 i8 o% [* d0 h6 h# E- ~
elif room【i】[j] == -1:4 N6 ^# n5 B O, n- F" I( K1 [
continue
else:9 f1 x* u/ S3 Z+ a; l
room【i】[j] = 0
# bfs all equipments locations to all avalibale locations
for i, j in equipments:
self.bfs(room, i, j)
2 ~) E1 T9 N% s
pos = [-1, -1]+ b4 A* z6 r6 J0 B: w! B2 ^4 V& Q
dis = 2**31 - 1
for i in xrange(m):& s8 N3 q# N3 R( p! E! j+ d$ d {
for j in xrange(n):) c/ O$ J8 [: |0 v+ r
if (i, j) in equipments or room【i】[j] < 0:! k7 ?3 z! P r6 x ~' j& o) Y
continue0 H7 g/ h. Z% Z7 U: S+ t6 P9 v
if room【i】[j] < dis:+ t% o- }/ Y7 p* U; W! \
dis = room【i】[j]
pos = [i, j]
return pos
4 {. ^6 a U9 A2 I
def bfs(self, room, i, j):7 h: F8 O2 p' m- P1 ^7 c
queue = collections.deque()
queue.append((i, j, 0))) _2 |2 w: W9 X A, Q. w; g( P
marked = set()
while queue:
mi, mj, distance = queue.popleft()
distance += 1( y. A4 k: `3 C% X X9 d; w
# up* m% g& Q- E# o$ N; m4 @
if mi > 0 and room[mi - 1][mj] != -1 and (mi - 1, mj) not in marked:6 Y6 }( {6 a1 B' r; \4 T% m! d
room[mi - 1][mj] += distance
marked.add((mi - 1, mj))8 ?! e- v+ h9 a0 x( d
queue.append((mi - 1, mj, distance))8 ~5 O: e9 Z! F( H2 n; |% V7 o
# down
if mi < len(room) - 1 and room[mi + 1][mj] != -1 and (mi + 1, mj) not in marked:( ^. v! F9 o3 m. B$ a. A3 ^8 c1 _
room[mi + 1][mj] += distance
marked.add((mi + 1, mj))- D2 E" S# i1 e6 Y+ {8 M, ~7 L6 x) K
queue.append((mi + 1, mj, distance))& _9 F0 A9 Y8 q% g
# left l. R& ^/ N8 @2 g
if mj > 0 and room[mi][mj - 1] != -1 and (mi, mj - 1) not in marked:1 s* i+ V5 i& e% m0 k
room[mi][mj - 1] += distance
marked.add((mi, mj - 1))" O9 v0 e, q) E- E5 x
queue.append((mi, mj - 1, distance)); x( E6 U' N. @& Z( y) C
# right
if mj < len(room[0]) - 1 and room[mi][mj + 1] != -1 and (mi, mj + 1) not in marked:
room[mi][mj + 1] += distance9 M ?! O6 Y/ I1 f
marked.add((mi, mj + 1))* V e% a/ f" s, f" i9 k- D& v7 s
queue.append((mi, mj + 1, distance))' G9 ~- s# h:

[Google] Shortest Manhattan Distance - Shuatiblog.com

Labels

Popular Posts