project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_81.go (1770B)

      1 package main
      2 
      3 import (
      4   "fmt"
      5   "io/ioutil"
      6   "strings"
      7   "strconv"
      8 )
      9 
     10 type Node struct {
     11   cost int
     12   distance int
     13   included bool
     14 }
     15 
     16 func dijkstra(matrix [][]Node) int {
     17   for count := 0; count < (80 * 80) - 1; count++ {
     18     min := 1<<31 - 1
     19     var min_x int
     20     var min_y int
     21 
     22     for x := 0; x < 80; x++ {
     23       for y := 0; y < 80; y++ {
     24         if matrix[x][y].included == false && matrix[x][y].distance <= min {
     25           min = matrix[x][y].distance
     26           min_x = x
     27           min_y = y
     28         }
     29       }
     30     }
     31 
     32     matrix[min_x][min_y].included = true
     33 
     34     for x := 0; x < 80; x++ {
     35       for y := 0; y < 80; y++ {
     36         if x + 1 < 80 {
     37           if (!matrix[x + 1][y].included) && matrix[x][y].distance != 1<<31 - 1 && matrix[x][y].distance + matrix[x + 1][y].cost < matrix[x + 1][y].distance {
     38             matrix[x + 1][y].distance = matrix[x][y].distance + matrix[x + 1][y].cost
     39           }
     40         }
     41 
     42 
     43         if y + 1 < 80 {
     44           if (!matrix[x][y + 1].included) && matrix[x][y].distance != 1<<31 - 1 && matrix[x][y].distance + matrix[x][y + 1].cost < matrix[x][y + 1].distance {
     45             matrix[x][y + 1].distance = matrix[x][y].distance + matrix[x][y + 1].cost
     46           }
     47         }
     48       }
     49     }
     50   }
     51 
     52   return matrix[79][79].distance
     53 }
     54 
     55 func main() {
     56   dat, _ := ioutil.ReadFile("./files/matrix_81.txt")
     57 
     58   var matrix [][]Node
     59 
     60   for _, r := range strings.Split(string(dat), "n") {
     61     var int_row []Node
     62 
     63     for _, r2 := range strings.Split(r, ",") {
     64       var n Node
     65       cost, _ := strconv.Atoi(r2)
     66       n.cost = cost
     67       n.distance = 1<<31 - 1
     68       n.included = false
     69       int_row = append(int_row, n)
     70     }
     71 
     72     matrix = append(matrix, int_row)
     73   }
     74 
     75   matrix[0][0].distance = matrix[0][0].cost
     76   fmt.Println(dijkstra(matrix))
     77 }