Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import scala.io.Source
- import java.io.PrintWriter
- import scala.collection.mutable.PriorityQueue
- import util.control.Breaks._
- /* The solution object. **/
- object MatrixPath extends App {
- // Read the input file
- val lines = Source.fromFile("in.txt").getLines
- val n = lines.next().toInt
- // a matrix of size NxN
- val matrix: Array[Array[Int]] = Array.ofDim[Int](n, n)
- for (x <- 0 until matrix.size) {
- val intArr = lines.next().split(" ")
- for (y <- 0 until intArr.size) {
- matrix(x)(y) = intArr(y).toInt
- }
- }
- class Node (val i: Int, val j: Int, val sum: Int) extends Ordered[Node] {
- def compare(that: Node): Int = that.sum.compare(this.sum)
- }
- val visited: Array[Array[Boolean]] = Array.ofDim(n, n)
- val queue = new PriorityQueue[Node]()
- def visit(i: Int, j: Int, sum: Int) {
- if (i < 0 || i >= n || j < 0 || j >= n || visited(i)(j)) {
- return
- }
- queue.enqueue(new Node( i, j, sum+matrix(i)(j) ))
- visited(i)(j) = true
- }
- def findMinPathSum(): Int = {
- var node: Node = new Node(0, 0, matrix(0)(0))
- queue.enqueue(node)
- breakable {
- while (!queue.isEmpty) {
- node = queue.head
- if (node.i == n - 1 && node.j == n - 1) { break }
- visit(node.i + 1, node.j, node.sum)
- visit(node.i - 1, node.j, node.sum)
- visit(node.i, node.j + 1, node.sum)
- visit(node.i, node.j - 1, node.sum)
- queue.dequeue()
- }
- }
- return node.sum
- }
- val answer = findMinPathSum()
- // Form and write the correct output
- val writer = new PrintWriter("out.txt", "UTF-8")
- try writer.print(answer.toString)
- finally writer.close
- }
- // EOF
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement