project-euler

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

Euler_83.go (2354B)

      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         if y + 1 < 80 {
     43           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 {
     44             matrix[x][y + 1].distance = matrix[x][y].distance + matrix[x][y + 1].cost
     45           }
     46         }
     47 
     48         if x - 1 >= 0 {
     49           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 {
     50             matrix[x - 1][y].distance = matrix[x][y].distance + matrix[x - 1][y].cost
     51           }
     52         }
     53 
     54         if y - 1 >= 0 {
     55           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 {
     56             matrix[x][y - 1].distance = matrix[x][y].distance + matrix[x][y - 1].cost
     57           }
     58         }
     59       }
     60     }
     61   }
     62 
     63   return matrix[79][79].distance
     64 }
     65 
     66 func main() {
     67   dat, _ := ioutil.ReadFile("./files/matrix_83.txt")
     68 
     69   var matrix [][]Node
     70 
     71   for _, r := range strings.Split(string(dat), "n") {
     72     var int_row []Node
     73 
     74     for _, r2 := range strings.Split(r, ",") {
     75       var n Node
     76       cost, _ := strconv.Atoi(r2)
     77       n.cost = cost
     78       n.distance = 1<<31 - 1
     79       n.included = false
     80       int_row = append(int_row, n)
     81     }
     82 
     83     matrix = append(matrix, int_row)
     84   }
     85 
     86   matrix[0][0].distance = matrix[0][0].cost
     87 
     88   fmt.Println(dijkstra(matrix))
     89 }