/
317.shortest-distance-from-all-buildings.kt
61 lines (61 loc) · 1.73 KB
/
317.shortest-distance-from-all-buildings.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution
typealias Point = Pair<Int,Int>
val dirs = listOf(-1 to 0,1 to 0, 0 to 1,0 to -1)
fun Solution.shortestDistance(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val zeros = mutableListOf<Point>()
for(i in 0 until m){
for(j in 0 until n){
if(grid[i][j]==0)
zeros.add(i to j)
}
}
val zeroMap = mutableMapOf<Point,Int>()
for(i in 0 until zeros.size){
zeroMap[zeros[i]] = i
}
val k = zeros.size
val lst = mutableListOf<IntArray>()
fun getDistance(p:Point):IntArray{
val current = mutableListOf(p to 0)
val visited = mutableSetOf(p)
val arr = IntArray(k) {-1}
while(current.size>0){
val (p,d) = current.removeAt(0)
val (x,y) = p
for((dx,dy) in dirs){
val nx = x + dx
val ny = y + dy
if(nx<0||ny<0) continue
if(nx>=m || ny>=n) continue
if(grid[nx][ny]!=0) continue
val pair = nx to ny
if(pair in visited) continue
visited.add(pair)
current.add(pair to d+1)
val i = zeroMap[pair]!!
arr[i] = d+1
}
}
return arr
}
for(i in 0 until m){
for(j in 0 until n){
if(grid[i][j]==1){
lst.add(getDistance(i to j))
}
}
}
var ret = Int.MAX_VALUE
loop@for(i in 0 until k){
var total = 0
for(j in 0 until lst.size){
if(lst[j][i]==-1) continue@loop
total += lst[j][i]
}
ret = Math.min(ret,total)
}
if(ret==Int.MAX_VALUE) return -1
return ret
}