Submission #423650

---

Source Code Expand

import scala.collection.immutable.Stack
import scala.annotation.tailrec

case class Graph(es: scala.collection.mutable.Map[Vertex, Seq[Edge]])
case class Vertex(s: Char, i: Int, j: Int)
case class Edge(v: Vertex)

  object Main{
    def main(args: Array[String]):Unit = {
      import scala.collection.mutable
      val graph = Graph(mutable.Map():mutable.Map[Vertex, Seq[Edge]])
      val scanner = new java.util.Scanner(System.in)
      val h = scanner.nextInt
      val w = scanner.nextInt

      val inputs = (0 until h).toArray.map{x => scanner.next.toArray}
      for{i <- (0 until h)
          j <- (0 until w)
      }(getFourWay(graph, inputs, h, w, i, j))
      val start = graph.es.keySet.filter(_.s == 's').head
      val goal = graph.es.keySet.filter(_.s == 'g').head
      if(dfs(graph, start, goal)) println("Yes")
      else println("No")
    }

    def getFourWay(graph:Graph ,arr2:Array[Array[Char]], h:Int, w:Int, i:Int, j:Int): Unit = {
      val edges = scala.collection.mutable.ArrayBuffer.empty[Edge]
      // 北(i-1, j), 東(i, j+1), 南(i+1, j), 西(i, j-1)
      if(i-1 >= 0){edges += Edge(Vertex(arr2(i-1)(j), i-1, j))}
      if(j+1 < w){edges += Edge(Vertex(arr2(i)(j+1), i, j+1))}
      if(i+1 < h){edges += Edge(Vertex(arr2(i+1)(j), i+1, j))}
      if(j-1 >= 0){edges += Edge(Vertex(arr2(i)(j-1), i, j-1))}
      graph.es += Vertex(arr2(i)(j), i, j) -> edges.toSeq
    }

    def dfs(g: Graph,  v: Vertex,  goal: Vertex): Boolean = {
      dfs(g,  goal, Set(),  Stack(v))
    }

    @tailrec
    def dfs(g: Graph, goal: Vertex, visited: Set[Vertex], stack: Stack[Vertex]): Boolean = {
      val (v, s) = stack.pop2
      if (v == goal) true
      else if (visited.contains(v) && s.nonEmpty) dfs(g, goal, visited + v, s)
      else if (visited.contains(v)) false
      else {
        g.es.get(v) match {
          case Some(e) => dfs(g, goal, visited + v, s.pushAll(e.reverseMap(_.v).filter(_.s != '#')))
          case _ if s.nonEmpty => dfs(g, goal, visited + v, s)
          case _ => false
        }
      }
    }

  
}

Submission Info

Compile Error

warning: there were two deprecation warnings; re-run with -deprecation for details
one warning found

Judge Result