Snippets
Created by
cia_rana
last modified
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 110 111 112 113 | package main
import (
"fmt"
"strings"
)
const sideLength = 4
type Queue []*Node
func (q *Queue) isEmpty() bool {
return len(*q) == 0
}
func (q *Queue) enqueue(node *Node) {
*q = append(*q, node)
}
func (q *Queue) dequeue() *Node {
if q.isEmpty() {
return nil
}
n := (*q)[0]
*q = (*q)[1:]
return n
}
type Graph struct {
maxCost int
nodes []*Node
}
type Node struct {
cost int
inCount int
neighborNodes []*Node
}
func makeGraph(rows []string) Graph {
hexHeight := sideLength * 2 - 1
// 六角形に整列されたノード(hexNode)を生成する
hexNodes := make([][]Node, hexHeight)
for i, row := range rows {
hexNodes[i] = make([]Node, 0)
for j := 0; j < len(row); j++ {
hexNodes[i] = append(hexNodes[i], Node{cost: 1, inCount: 0, neighborNodes: make([]*Node, 0)})
}
}
// ノード間を繋ぎ,有向グラフを構築する
graph := Graph{maxCost: 0, nodes: make([]*Node, 0)}
for i, row := range rows {
delta_up := (hexHeight - i) / sideLength
delta_down := (i + 1) / sideLength
for j, c := range row {
for _, p := range [][]int{{i-1, j-delta_up}, {i-1, j+1-delta_up}, {i, j-1}, {i, j+1}, {i+1, j-delta_down}, {i+1, j+1-delta_down}} {
if 0 <= p[0] && p[0] < hexHeight && 0 <= p[1] && p[1] < len(rows[p[0]]){
if uint8(c) < rows[p[0]][p[1]] {
// 隣接ノードを加える
hexNodes[i][j].neighborNodes = append(hexNodes[i][j].neighborNodes, &hexNodes[p[0]][p[1]])
} else if uint8(c) > rows[p[0]][p[1]] {
// 入次数をカウントする
hexNodes[i][j].inCount++
}
}
}
// hexNodeを有効グラフのノードとして加える
graph.nodes = append(graph.nodes, &hexNodes[i][j])
}
}
return graph
}
func solve() int {
var s string
fmt.Scan(&s)
rows := strings.Split(s, "/")
graph := makeGraph(rows)
// 入次数0のノードを集めるキュー
zeroQueue := new(Queue)
for _, node := range graph.nodes {
if node.inCount == 0{
zeroQueue.enqueue(node)
}
}
for node := zeroQueue.dequeue(); node != nil; node = zeroQueue.dequeue() {
for _, neighborNode := range (*node).neighborNodes {
if (*neighborNode).cost < (*node).cost + 1 {
(*neighborNode).cost = (*node).cost + 1
if graph.maxCost < (*neighborNode).cost {
graph.maxCost = (*neighborNode).cost
}
}
(*neighborNode).inCount--
if (*neighborNode).inCount == 0 {
zeroQueue.enqueue(neighborNode)
}
}
}
return graph.maxCost
}
func main(){
fmt.Print(solve())
}
|
Comments (0)
You can clone a snippet to your computer for local editing. Learn more.