-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
1162-as-far-from-land-as-possible.kt
75 lines (60 loc) · 2.03 KB
/
1162-as-far-from-land-as-possible.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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// BFS solution
class Solution {
fun maxDistance(grid: Array<IntArray>): Int {
fun isValid(i: Int, j: Int) = i in (0..grid.lastIndex) && j in (0..grid[0].lastIndex) && grid[i][j] == 0
val q = ArrayDeque<Pair<Int, Int>>()
var distance = -1
for (i in grid.indices) {
for (j in grid[0].indices) {
if (grid[i][j] == 1)
q.add(i to j)
}
}
while (q.isNotEmpty()) {
distance++
val size = q.size
repeat (size) {
val (i,j) = q.poll()
for (dir in dirs) {
val nextI = i + dir[0]
val nextJ = j + dir[1]
if (isValid(nextI, nextJ)) {
q.add(nextI to nextJ)
grid[nextI][nextJ] = 1
}
}
}
}
return if (distance > 0) distance else -1
}
val dirs = arrayOf(
intArrayOf(0, 1),
intArrayOf(0, -1),
intArrayOf(1, 0),
intArrayOf(-1, 0)
)
}
//DP solution
class Solution {
fun maxDistance(grid: Array<IntArray>): Int {
val defaultValue = 100 + 100 + 1
for (i in grid.indices) {
for (j in grid[0].indices) {
if (grid[i][j] == 1) continue
grid[i][j] = defaultValue
if(i > 0) grid[i][j] = minOf(grid[i][j], grid[i - 1][j] + 1)
if(j > 0) grid[i][j] = minOf(grid[i][j], grid[i][j - 1] + 1)
}
}
var res = 0
for (i in grid.lastIndex downTo 0) {
for (j in grid[0].lastIndex downTo 0) {
if (grid[i][j] == 1) continue
if(i < grid.lastIndex) grid[i][j] = minOf(grid[i][j], grid[i + 1][j] + 1)
if(j < grid[0].lastIndex) grid[i][j] = minOf(grid[i][j], grid[i][j + 1] + 1)
res = maxOf(res, grid[i][j])
}
}
return if (res == defaultValue) -1 else res - 1
}
}