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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
package main
import (
"bufio"
"container/heap"
"fmt"
"os"
)
type Node struct {
risk byte
x, y, cost int
index int
}
type NodeQueue []*Node
func (pq NodeQueue) Len() int { return len(pq) }
func (pq NodeQueue) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq NodeQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *NodeQueue) Push(x interface{}) {
item := x.(*Node)
item.index = len(*pq)
*pq = append(*pq, item)
}
func (pq *NodeQueue) Pop() interface{} {
p := *pq
l := len(p) - 1
item := p[l]
item.index = -1
p[l] = nil
*pq = p[0:l]
return item
}
func (pq *NodeQueue) Update(n *Node, cost int) {
n.cost = cost
heap.Fix(pq, n.index)
}
var (
costs [][]Node
nq = make(NodeQueue, 1)
size int
fullsize int
)
func calculateTentativeDistance(x, y, cost int) {
if x < 0 || x >= size || y < 0 || y >= size {
return
}
cost += int(costs[y][x].risk)
if costs[y][x].cost == 0 {
costs[y][x].cost = cost
heap.Push(&nq, &costs[y][x])
} else if cost < costs[y][x].cost {
nq.Update(&costs[y][x], cost)
}
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
line := scanner.Text()
size = len(line)
fullsize = size * 5
for y := 0; y < fullsize; y++ {
costs = append(costs, make([]Node, fullsize))
for x := 0; x < fullsize; x++ {
costs[y][x].x = x
costs[y][x].y = y
costs[y][x].index = -1
}
}
for y := 0; y < size; y++ {
for x := 0; x < size; x++ {
costs[y][x].risk = line[x] - '0'
for i := 1; i < 5; i++ {
costs[y][x+i*size].risk = (costs[y][x+(i-1)*size].risk % 9) + 1
}
for j := 1; j < 5; j++ {
for i := 0; i < 5; i++ {
costs[y+j*size][x+i*size].risk = (costs[y+(j-1)*size][x+i*size].risk % 9) + 1
}
}
}
scanner.Scan()
line = scanner.Text()
}
size = fullsize
costs[0][0].cost = 0
nq[0] = &costs[0][0]
heap.Init(&nq)
for {
n := heap.Pop(&nq).(*Node)
if n.x == size-1 && n.y == size-1 {
fmt.Println(n.cost)
break
}
calculateTentativeDistance(n.x-1, n.y, n.cost)
calculateTentativeDistance(n.x+1, n.y, n.cost)
calculateTentativeDistance(n.x, n.y-1, n.cost)
calculateTentativeDistance(n.x, n.y+1, n.cost)
}
}
|
