assignment5.scala

assignment5.scala

package ru.tinkoff.main

import scala.annotation.tailrec
import scala.collection.immutable.SortedSet
import scala.collection.mutable

/*
5. Кратчайший маршрут 

Швеция богата природными ресурсами, и шведы очень любят соревнования по ориентированию на местности. Житель провинции Смоланд Андрс Линдгрен с детства мечтал победить в таких соревнованиях. Он много тренировался, со временем научился быстро бегать и легко преодолевать препятствия, однако всякий раз его подводил выбор маршрута. В старших классах он попал в сильную группу по информатике и, окончив школу, написал программу для смартфона, которая по карте рассчитывала кратчайший маршрут между двумя точками с учетом препятствий. С помощью этой программы Андерсу удалось выиграть соревнования и исполнить свою заветную мечту. Он был так счастлив, что сразу же поделился радостью на своей странице в Facebook и рассказал о чудо-программе. В Швеции нашлось много желающих установить такую программу на свой смартфон, и ею заинтересовались в фирме «Эрикссон». Представители фирмы обратились к Андерсу Линдгрену с предложением продать программу, однако он запросил слишком высокую цену. Теперь фирма "Эрикссон" устраивает конкурс на лучшую навигационную программу для смартфона, рассчитывающую кратчайший путь до указанного пункта с учетом препятствий. Вам предоставляется уникальная возможность принять участие в конкурсе, несмотря на то, что Вы не являететсь гражданином Швеции. 

Необходимо написать программу, которая на вход принимает карту местности и выводит время прохождения по кратчайшему маршруту или "-1", если маршрут пройти нельзя. 

Карта местности представляет собой двухмерную сетку с условными обозначениями сложности прохождения каждой клетки. 


Входные данные: 
На вход программы подаются текстовые строки, описывающие карту местности следующим образом: 
— первая строка - два числа (от 1 до 1000), записанные через пробел. Это ширина и высота карты в ячейках. 
— далее каждая строка представляет собой одну строку карты (один символ — одна ячейка) 
— символов в строке может быть больше, чем ширина карты, в этом случае оставшиеся до конца строки символы отбрасываются 
— все строки разделяются символом перевода строки "\n" (0x0A, формат UNIX) 

Ячейки бывают четырех видов: 
1. Проходимые (с указанием времени прохождения данной клетки в условных единицах). Например, "0", "1" или "5". Для простоты визуального восприятия клетка с временем прохождения 1 может записываться в виде пробела: " ". 
2. Непроходимые (через которые нельзя пройти ни в одну строну). Обозначаются как "x" (английская раскладка, нижний регистр) 
3. Начало маршрута (не участвует в подсчете времени прохождения). Обозначается как "A" (английская раскладка, верхний регистр) 
4. Конец маршрута (считается, что время прохождения этой клетки равно 1). Обозначается как "B" (английская раскладка, верхний регистр) 

Выходные данные:
В единственной строке выведите время прохождения по кратчайшему маршруту или "-1", если маршрут пройти нельзя. 

 */
object Assignment5 {
  def main(args: Array[String]): Unit = {
    val line1 = "5 5"
    val line2 =
      """A3214
        |234x0
        |43x34
        |xx300
        |B1234   sfsdfsdf
      """.stripMargin

    val nonFoundAnswer = -1
    val rowsNum = line1.split(" ")(0).toInt
    val columnsNum = line1.split(" ")(1).toInt
    case class Point(
                      x: Int,
                      y: Int,
                      isStart: Boolean,
                      isEnd: Boolean,
                      isBlock: Boolean,
                      cost: Int
                    )
    val startSym = "A"
    val endSym = "B"
    val blockSym = "x"

    def getCost(sym: String): Int = {
      sym match {
        case x if x == endSym => 1
        case x if x == startSym => 0
        case x if x == blockSym => -1
        case " " => 1
        case x => x.toInt
      }
    }

    val symbolsTable = for {
      line <- line2.trim.split("\n").filter(_.nonEmpty).take(rowsNum)
    } yield line.split("").take(columnsNum)

    val points = (0 until columnsNum).map(y =>
      (0 until rowsNum).map(x => {
        val el = symbolsTable(y)(x)
        Point(
          x,
          y,
          el == startSym,
          el == endSym,
          el == blockSym,
          getCost(el)
        )
      }).toArray
    ).toArray

    val grh: Map[Point, Array[Point]] = (for (
      y <- 0 until columnsNum;
      x <- 0 until rowsNum
    ) yield {
      val point = points(y)(x)
      if (point.isBlock || point.isEnd) {
        point -> Array[Point]()
      } else {
        val neighbors = mutable.ArrayBuffer[Point]()
        if (x - 1 >= 0) neighbors += points(y)(x - 1)
        if (y - 1 >= 0) neighbors += points(y - 1)(x)
        if (x + 1 < columnsNum) neighbors += points(y)(x + 1)
        if (y + 1 < rowsNum) neighbors += points(y + 1)(x)

        point -> neighbors.filterNot(_.isBlock).toArray
      }
    }).toMap

    val startPoint = grh.keys.filter(_.isStart).head

    @tailrec
    def searchPath(nonVisitedWithScore: SortedSet[(Point, Long)], visited: Set[Point]): Long = {
      if (nonVisitedWithScore.isEmpty) {
        nonFoundAnswer
      } else {
        val (pointWithMinScore, score) = nonVisitedWithScore.head
        val neighbors = grh.get(pointWithMinScore).head.filterNot(p => visited.contains(p))

        if (neighbors.exists(x => x.isEnd)) {
          score + 1
        } else {
          val addingNonVisited = neighbors.map(p => p -> (score + p.cost)).toMap
          val nonVisitedWithoutMinPointCost = nonVisitedWithScore - (pointWithMinScore -> score)
          val newNonVisited = nonVisitedWithoutMinPointCost ++ addingNonVisited
          val newVisited = visited + pointWithMinScore
          searchPath(newNonVisited, newVisited)
        }
      }
    }

    val orderForNonVisited: Ordering[(Point, Long)] = (x, y) => x._2.compare(y._2)
    val result = searchPath(SortedSet(startPoint -> 0L)(orderForNonVisited), Set(startPoint))

    println(result)
  }
}