-
Notifications
You must be signed in to change notification settings - Fork 485
/
1368.go
39 lines (36 loc) · 1.09 KB
/
1368.go
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
func minCost(grid [][]int) int {
m, n := len(grid), len(grid[0])
q := [][]int{{0, 0, 0}}
d := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
vis := make([]bool, m * n)
dist := make([]int, m * n)
for i := 0; i < m * n; i++ {
dist[i] = 1000000000
}
dist[0] = 0
for len(q) > 0 {
t := q[0]
q = q[1:]
step, x, y := t[0], t[1], t[2]
if vis[x * n + y] {
continue
}
vis[x * n + y] = true
for i := 1; i <= 4; i++ {
nx, ny := x + d[i - 1][0], y + d[i - 1][1]
new_dist := step
if grid[x][y] != i {
new_dist++
}
if nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx * n + ny] > new_dist {
dist[nx * n + ny] = new_dist
if grid[x][y] != i {
q = append(q, []int{dist[nx * n + ny], nx, ny})
} else {
q = append([][]int{{dist[nx * n + ny], nx, ny}}, q...)
}
}
}
}
return dist[m * n - 1]
}