import GraphBFS.bfs
object Maze extends App {
  def solveMaze(maze: List[String]):Option[String] = {
    type node = Int
    val width = maze.head.length()
    val height = maze.length
//    val start =
//    maze.map()
    def findStart(maze: List[String], r: Int, start: (Int, Int), end: (Int, Int)): ((Int, Int), (Int,Int)) = {
      def inner(row: String, c: Int, start: (Int, Int), end: (Int, Int)): ((Int, Int), (Int,Int)) = {
        if (c == width) (start, end)
        else {
          val start_ = if (row.head.equals('s')) (r, c) else start
          val end_ = if (row.head.equals('e')) (r, c) else end
          inner(row.tail, c+1, start_, end_)
        }
      }
      if (r == height) (start, end)
      else {
        val se = inner(maze.head, 0, start, end)
        findStart(maze.tail, r + 1, se._1, se._2)
      }
    }

    def cre(Maze: List[String], r: Int, Maze_ : List[Int]): List[Int] = {
      def inner(row: String, r: Int, c: Int, row_ : List[Int]): List[Int] = {
        if (c == width)
          row_
        else
        if (row.head.equals(' ')) inner(row.tail, r, c+1, (r*1000 + c)::row_) else inner(row.tail, r, c+1, row_)
      }
      if (r == height) Maze_
      else
        cre(Maze.tail, r + 1, inner(Maze.head, r, 0, Maze_))
      }

    val (start, end) = findStart(maze, 0, (0, 0), (0, 0))
    val maze_ = (end._1*1000+end._2 :: start._1*1000+start._2 :: cre(maze, 0, Nil)).toSet//.flatMap(_.toList)).toSet
//    println(time((end :: start :: cre(maze, 0, Nil)).toSet))
//    print(maze_)


    def nbrs(node: Int): Set[Int] = {
        Set((node/1000)*1000 + node%1000-1, (node/1000)*1000 + node%1000 + 1, (node/1000 -1)*1000 + node%1000, (node/1000 + 1)*1000 + node%1000).filter(maze_.contains(_))
//      case (a,b) => Set((a, b - 1), (a, b + 1), (a - 1, b), (a + 1, b)).filter(maze_.contains(_))
    }

    val myGraph = time {maze_.map(x => (x, nbrs(x))).toMap}

    val myNbrs = (n: Int) => myGraph.getOrElse(n, Set())

    def getDir(c: Int, p: Int):String = {
        val c1 = c/1000
        val c2 = c%1000
        val p1 = p/1000
        val p2 = p%1000
//        println(c1,c2, p1,p2)
        if (c1 > p1) "d"
        else if (c1 < p1) "u"
        else if (c2 > p2) "r"
        else if (c2 < p2) "l"
        else ""
    }


    val (parent: Map[Int, Int], distance) = time{bfs(myGraph, start._1*1000+start._2)}
//    println(parent)

    def traverse(crr: Int, dleft: Int, path: List[String]): List[String] = dleft match{
      case 0 => path
      case _ =>
//        println(getDir(crr, parent(crr)))
        traverse(parent(crr), dleft - 1, getDir(crr, parent(crr)) :: (path))
    }
    if (parent isDefinedAt end._1*1000+end._2){
      Some(traverse(end._1*1000+end._2, distance(end._1*1000+end._2), Nil).mkString)
    }
    else None

    }
  val maze = List("xxxxxxxxxxxxxxxxxx",
    "x    x      x   ex",
    "x    x   x  x xxxx",
    "x        x  x    x",
    "xs   x   x       x",
    "xxxxxxxxxxxxxxxxxx")
//  println(solveMaze(maze))

  def time[R](block: => R): R = {
    val t0 = System.currentTimeMillis()
    val result = block    // call-by-name
    val t1 = System.currentTimeMillis()
    println("Elapsed time: " + (t1 - t0) + "ms")
    result
  }
  val maze250 = List("x" * 250):::List("xs" + " " * 247 + "x"):::List.fill(246)("x"+" " * 248+"x"):::List("x" + " " * 247 + "ex"):::List("x" * 250)
  println(time(solveMaze(maze250)))

}







import scala.collection.immutable

object GraphBFS {

  def bfs[V](nbrs: V => Set[V], src: V) = {

    def expand(frontier: Set[V], parent: Map[V, V]): (Set[V], Map[V, V]) = {

      val parent_ = frontier
        .flatMap(x => nbrs(x).filter(j => !parent.contains(j)).flatMap(g => Map(g -> x)))
//      val frontier_ = frontier.flatMap(nbrs).filter(!parent.keySet.contains(_))
      val frontier_ = frontier.flatMap(nbrs).filter(!parent.contains(_))
//        .diff(parent.keySet)

        //.flatMap(_.toSet)
//      def map(f1: Set[V], f2: Set[V], map: Map[V, V]):Null = (f1, f2) match{
//        case (h1::t1, h2::t2) =>
//      }
//      val parent_ = (frontier zip frontier_).toMap


//      val parent_ = frontier.flatMap(x => nbrs(x).filter(!parent.keySet.contains(_)).map((_, x))).toMap ++ parent

//  map{x =>
//        try{
//          nbrs(x).diff(parent.keySet).map((_, x))
//        } catch {
//          case e: Exception =>
//            Nil
//        }
//      }.flatMap(_.toSet).toMap ++ parent

      (frontier_, parent ++ parent_)
    }

    def iterate(frontier: Set[V], parent: Map[V, V], distance: Map[V, Int], d: Int):(Map[V, V], Map[V, Int]) =
      if (frontier.isEmpty)
        (parent, distance)
      else {
        val (frontier_, parent_) = expand(frontier, parent)
        val distance_ = distance ++ frontier.map(_ -> d)
//        val distance_ = distance ++ frontier.flatMap(a => Map(a -> d))

        iterate(frontier_, parent_, distance_, d + 1)
      }

    iterate(Set(src), Map(src -> src), Map(), 0)
  }

}