pe83.go

package main

import (
	"bufio"
	"fmt"
	"github.com/yourbasic/graph"
	"log"
	"os"
	"strconv"
	"strings"
	"time"
)

func main() {
	start := time.Now()

	gC := make([][]int64,0)

	file, err := os.Open("m83.txt")
	if err != nil {
		log.Fatal(err)
	}
	defer file.Close()

	scanner := bufio.NewScanner(file)
	for scanner.Scan() {
		split := strings.Split(scanner.Text(),",")
		c := make([]int64,len(split))
		for k,v := range split{
			c[k] ,_ = strconv.ParseInt(v,10,64)
		}
		gC = append(gC,c)
	}

	if err := scanner.Err(); err != nil {
		log.Fatal(err)
	}

	inRow := len(gC)
	g := graph.New(inRow * inRow + 1)
	for row := range gC{
		if row == inRow - 1{ // last row; Nothing is downer
			for col := range gC[row]{
				g.AddCost(row * inRow + col,row * inRow + col + 1,gC[row][col]) // also note that the very left and bottom nod is connected to exit nod
				g.AddCost(row * inRow + col,row * inRow + col - inRow,gC[row][col]) // connect to upper row
				if col != 0{
					g.AddCost(row * inRow + col,row * inRow + col - 1,gC[row][col]) // connect to nod before row
				}
			}
		}else if row == 0{ // first row does not have upper rows
			for col := range gC[row]{
				g.AddCost(row * inRow + col,row * inRow + col + inRow,gC[row][col]) // connects the nod to the nod below it
				if col != inRow - 1{
					g.AddCost(row * inRow + col,row * inRow + col + 1,gC[row][col]) // connect to left
				}
				if col != 0{
					g.AddCost(row * inRow + col,row * inRow + col - 1,gC[row][col]) // connect to nod before row
				}
			}
		} else{
			for col := range gC[row]{
				g.AddCost(row * inRow + col,row * inRow + col + inRow,gC[row][col]) // connects the nod to the nod below it
				g.AddCost(row * inRow + col,row * inRow + col - inRow,gC[row][col]) // connect to upper row
				if col != 0{
					g.AddCost(row * inRow + col,row * inRow + col - 1,gC[row][col]) // connect to left
				}
				if col != inRow - 1{ // connect to right
					g.AddCost(row * inRow + col,row * inRow + col + 1,gC[row][col])
				}
			}
		}
	}
	_,min := graph.ShortestPath(g,0,inRow * inRow )
	fmt.Println("Passed: ",time.Since(start))
	fmt.Println(min)
}