project-euler

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

Euler_82.go (2511B)

      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         if y - 1 >= 0 {
     50           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 {
     51             matrix[x][y - 1].distance = matrix[x][y].distance + matrix[x][y - 1].cost
     52           }
     53         }
     54       }
     55     }
     56   }
     57 
     58   min := 1<<31 - 1
     59 
     60   for y := 0; y < 80; y++ {
     61     if matrix[79][y].distance <= min {
     62       min = matrix[79][y].distance
     63     }
     64 
     65     if matrix[79][y].distance == 1<<31 - 1 {
     66       panic("!")
     67     }
     68   }
     69 
     70   return min
     71 }
     72 
     73 func main() {
     74   dat, _ := ioutil.ReadFile("./files/matrix_82.txt")
     75 
     76   min :=1<<31 - 1
     77 
     78   for y := 0; y < 80; y++ {
     79     var matrix [][]Node
     80 
     81     for _, r := range strings.Split(string(dat), "n") {
     82       var int_row []Node
     83 
     84       for _, r2 := range strings.Split(r, ",") {
     85         var n Node
     86         cost, _ := strconv.Atoi(r2)
     87         n.cost = cost
     88         n.distance = 1<<31 - 1
     89         n.included = false
     90         int_row = append(int_row, n)
     91       }
     92 
     93       matrix = append(matrix, int_row)
     94     }
     95 
     96     matrix[0][y].distance = matrix[0][y].cost
     97     if y > 0 {
     98       fmt.Println(matrix[0][y - 1].distance)
     99     }
    100 
    101     potential_min := dijkstra(matrix)
    102 
    103     fmt.Println(potential_min)
    104 
    105     if potential_min <= min {
    106       min = potential_min
    107     }
    108   }
    109 
    110   fmt.Println(min)
    111 }