[Google] Shortest Manhattan Distance - Shuatiblog.com

[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的距离矩阵， 找距离矩阵中的最小值， 返回该点坐标。

1.     def get_location(self, room):3 C+ M: r  m6 t: d( P! |& g
2.         '''
3.         time: O(n * m * k) k is num of equipments
4.         space: O(k)
5.         '''
6.         m, n = len(room), len(room[0])& K2 |  X4 r9 D4 \* N! Y
7.         equipments = set()# H. A) l' D" x) c! S
8.         # find all equipments in the room
9.         for i in xrange(m):! L4 x/ Q4 E- |5 {
10.             for j in xrange(n):
11.                 if room【i】[j] == 0:8 c7 R& G: v/ L/ g( f: c6 b
12.                     equipments.add((i, j))7 i8 o% [* d0 h6 h# E- ~
13.                 elif room【i】[j] == -1:4 N6 ^# n5 B  O, n- F" I( K1 [
14.                     continue
15.                 else:9 f1 x* u/ S3 Z+ a; l
16.                     room【i】[j] = 0
17.         # bfs all equipments locations to all avalibale locations
18.         for i, j in equipments:
19.             self.bfs(room, i, j)
20.         2 ~) E1 T9 N% s
21.         pos = [-1, -1]+ b4 A* z6 r6 J0 B: w! B2 ^4 V& Q
22.         dis = 2**31 - 1
23.         for i in xrange(m):& s8 N3 q# N3 R( p! E! j+ d$ d  {
24.             for j in xrange(n):) c/ O$ J8 [: |0 v+ r
25.                 if (i, j) in equipments or room【i】[j] < 0:! k7 ?3 z! P  r6 x  ~' j& o) Y
26.                     continue0 H7 g/ h. Z% Z7 U: S+ t6 P9 v
27.                 if room【i】[j] < dis:+ t% o- }/ Y7 p* U; W! \
28.                     dis = room【i】[j]
29.                     pos = [i, j]
30.         return pos
31. 4 {. ^6 a  U9 A2 I
32.     def bfs(self, room, i, j):7 h: F8 O2 p' m- P1 ^7 c
33.         queue = collections.deque()
34.         queue.append((i, j, 0))) _2 |2 w: W9 X  A, Q. w; g( P
35.         marked = set()
36.         while queue:
37.             mi, mj, distance = queue.popleft()
38.             distance += 1( y. A4 k: `3 C% X  X9 d; w
39.             # up* m% g& Q- E# o$ N; m4 @
40.             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
41.                 room[mi - 1][mj] += distance
42.                 marked.add((mi - 1, mj))8 ?! e- v+ h9 a0 x( d
43.                 queue.append((mi - 1, mj, distance))8 ~5 O: e9 Z! F( H2 n; |% V7 o
44.             # down
45.             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 _
46.                 room[mi + 1][mj] += distance
47.                 marked.add((mi + 1, mj))- D2 E" S# i1 e6 Y+ {8 M, ~7 L6 x) K
48.                 queue.append((mi + 1, mj, distance))& _9 F0 A9 Y8 q% g
49.             # left  l. R& ^/ N8 @2 g
50.             if mj > 0 and room[mi][mj - 1] != -1 and (mi, mj - 1) not in marked:1 s* i+ V5 i& e% m0 k
51.                 room[mi][mj - 1] += distance
52.                 marked.add((mi, mj - 1))" O9 v0 e, q) E- E5 x
53.                 queue.append((mi, mj - 1, distance)); x( E6 U' N. @& Z( y) C
54.             # right
55.             if mj < len(room[0]) - 1 and room[mi][mj + 1] != -1 and (mi, mj + 1) not in marked:
56.                 room[mi][mj + 1] += distance9 M  ?! O6 Y/ I1 f
57.                 marked.add((mi, mj + 1))* V  e% a/ f" s, f" i9 k- D& v7 s
58.                 queue.append((mi, mj + 1, distance))' G9 ~- s# h: