HackerRank - Snakes and Ladders: The Quickest Way Up

• 問題URL: https://www.hackerrank.com/challenges/the-quickest-way-up/copy-from/191792908
• bfsを使用して最小パスを取得する
• 隣接リストの作り方にひと工夫必要だった。盤面は二次元だがリストは一次元で作成する。参考：http://theoryofprogramming.com/2014/12/25/snakes-and-ladders-game-code/

package main
 
 import (
     "bufio"
     "fmt"
     "io"
     "os"
     "strconv"
     "strings"
 )
 
 // Complete the quickestWayUp function below.
 type Queue []int32
 func (q *Queue)Enque(s int32){
     *q=append(*q,s)
 }
 func (q *Queue)Deque()(int32,error){
     if q.isEmpty(){
         return -1,fmt.Errorf("the q is empty")
     }
     v:=(*q)[0]
     *q=(*q)[1:]
     return v,nil
 }
 func (q *Queue)Peek()(int32,error){
     if q.isEmpty(){
         return -1,fmt.Errorf("the q is empty")
     }
     return (*q)[len(*q)],nil
 }
 func (q *Queue)Size()int{
     return len(*q)
 }
 func (q *Queue)isEmpty()bool{
     return q.Size()==0
 }
 func NewQueue()*Queue{
     s:=new(Queue)
     return s
 }
 var color []int32
 var M [][]int32
 var Q *Queue
 var d []int32
 var n int32
 //color white:-1,gray:0,black:1
 const(
     white=-1
     gray=0
     black=1
     INFTY=-1
     )
 func bfs(s int32){ //s=start index
     color[s]=gray
     d[s]=0
     Q.Enque(s)
     for !Q.isEmpty(){
         u,e:=Q.Deque()
         if e!=nil{
             panic(e)
         }
         for _,v:=range M[u]{
             if color[v]==white{
                 color[v]=gray
                 d[v]=d[u]+1
                 Q.Enque(v)
             }
         }
         color[u]=black
         //fmt.Println("Q",Q)
     }
 }
 // Init initializes variables for bfs.
 func Init(){
     Q = NewQueue()
     d=make([]int32,n)
     color=make([]int32,n)
     var i int32
     for i=0;i<n;i++{
         color[i]=white
         d[i]=INFTY
     }
 }
 func containsInLadStart(x int32,sl [][]int32)int32{
     for i:=0;i<len(sl);i++{
         if x==sl[i][0]{
             return int32(i)
         }
     }
     return -1
 }
 func containsInSnakeStart(x int32,sl [][]int32)int32{
     for i:=0;i<len(sl);i++{
         if x==sl[i][0]{
             return int32(i)
         }
     }
     return -1
 }
 func quickestWayUp(ladders [][]int32, snakes [][]int32) int32 {
     n=100
     M=make([][]int32,n)
     var i,j int32
     for i=0;i<n;i++{
         if k:=containsInLadStart(i,ladders);k>=0 && ladders[k][0]==i{
             continue
         }else if k:=containsInSnakeStart(i,snakes);k>=0 && snakes[k][0]==i{
             continue
         }
         for j=1;j<=6;j++{
             t:=i+j
             if k:=containsInLadStart(t,ladders);k>=0{
                 M[i]=append(M[i],ladders[k][1])
             }else if k:=containsInSnakeStart(t,snakes);k>=0{
                 M[i]=append(M[i],snakes[k][1])
             }else if i+j<100{
                 M[i]=append(M[i],t)
             }
         }
     }
     // fmt.Println("ladders",ladders)
     // fmt.Println("snakes",snakes)
     // for i=0;i<n;i++{
     //     fmt.Println(i,M[i])
     // }
     // fmt.Println(containsInLadStart(31,ladders))
     Init()
     bfs(0)
     //fmt.Println("d",d)
     return d[99]
 }
 
 func main() {
     reader := bufio.NewReaderSize(os.Stdin, 1024 * 1024)
 
     stdout, err := os.Create(os.Getenv("OUTPUT_PATH")) // 
     checkError(err)
 
     defer stdout.Close()
 
     writer := bufio.NewWriterSize(stdout, 1024 * 1024)
 
     tTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
     checkError(err)
     t := int32(tTemp)
 
     for tItr := 0; tItr < int(t); tItr++ {
         nTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
         checkError(err)
         n := int32(nTemp)
 
         var ladders [][]int32
         for i := 0; i < int(n); i++ {
             laddersRowTemp := strings.Split(readLine(reader), " ")
 
             var laddersRow []int32
             for _, laddersRowItem := range laddersRowTemp {
                 laddersItemTemp, err := strconv.ParseInt(laddersRowItem, 10, 64)
                 checkError(err)
                 laddersItem := int32(laddersItemTemp)-1
                 laddersRow = append(laddersRow, laddersItem)
             }
 
             if len(laddersRow) != int(2) {
                 panic("Bad input")
             }
 
             ladders = append(ladders, laddersRow)
         }
 
         mTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
         checkError(err)
         m := int32(mTemp)
 
         var snakes [][]int32
         for i := 0; i < int(m); i++ {
             snakesRowTemp := strings.Split(readLine(reader), " ")
 
             var snakesRow []int32
             for _, snakesRowItem := range snakesRowTemp {
                 snakesItemTemp, err := strconv.ParseInt(snakesRowItem, 10, 64)
                 checkError(err)
                 snakesItem := int32(snakesItemTemp)-1
                 snakesRow = append(snakesRow, snakesItem)
             }
 
             if len(snakesRow) != int(2) {
                 panic("Bad input")
             }
 
             snakes = append(snakes, snakesRow)
         }
 
         result := quickestWayUp(ladders, snakes)
 
         fmt.Fprintf(writer, "%d\n", result)
     }
 
     writer.Flush()
}
 
func readLine(reader *bufio.Reader) string {
     str, _, err := reader.ReadLine()
     if err == io.EOF {
         return ""
     }
 
     return strings.TrimRight(string(str), "\r\n")
 }
 
func checkError(err error) {
     if err != nil {
         panic(err)
     }
 }