Submission #423655

---

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(start,graph).contains(goal)) println("YES")
      else println("No")
      //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(start: Vertex, g: Graph): List[Vertex] = {
      def dfs0(v: Vertex, visited: List[Vertex]): List[Vertex] = {
        if (visited.contains(v))
          visited
        else {
          val neighbours:List[Edge] = (g.es(v) filterNot visited.contains).toList
          neighbours.filter(_.v.s != '#').foldLeft(v :: visited)((b,a) => dfs0(a.v,b))
        }
      }
      dfs0(start,List()).reverse
  }

}

Submission Info

Judge Result