Submission #423649

---

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(dfsRec(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 dfsRec(g: Graph, v: Vertex, goal: Vertex, visited: Set[Vertex] = Set()): Boolean = {
      if (v == goal) true
      else if (visited.contains(v)) false
      else g.es.get(v).exists(_.filter(e => e.v.s != '#').exists(e => dfsRec(g, e.v, goal, visited + v)))
    }
}

Submission Info

Judge Result