Submission #423656


Source Code Expand

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

case class Graph(es: scala.collection.mutable.Map[Vertex, List[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, List[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.ListBuffer.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.toList
    }

    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
          neighbours.filter(_.v.s != '#').foldLeft(v :: visited)((b,a) => dfs0(a.v,b))
        }
      }
      dfs0(start,List()).reverse
  }

}

Submission Info

Submission Time
Task A - 深さ優先探索
User ababup1192
Language Scala (2.11.5)
Score 0
Code Size 1946 Byte
Status WA
Exec Time 2040 ms
Memory 146408 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
WA × 2
AC × 19
WA × 4
TLE × 60
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt WA 1126 ms 48316 KB
00_min_02.txt AC 1120 ms 47920 KB
00_min_03.txt AC 1113 ms 47936 KB
00_min_04.txt AC 1129 ms 47880 KB
00_min_05.txt WA 1097 ms 47852 KB
00_min_06.txt AC 1115 ms 48188 KB
00_min_07.txt AC 1121 ms 48272 KB
00_min_08.txt AC 1109 ms 47972 KB
00_sample_01.txt AC 1115 ms 47836 KB
00_sample_02.txt WA 1117 ms 48360 KB
00_sample_03.txt AC 1124 ms 48024 KB
00_sample_04.txt WA 1146 ms 47892 KB
00_sample_05.txt AC 1127 ms 47864 KB
01_rnd_00.txt TLE 2034 ms 141356 KB
01_rnd_01.txt TLE 2033 ms 144112 KB
01_rnd_02.txt TLE 2033 ms 144160 KB
01_rnd_03.txt TLE 2034 ms 143908 KB
01_rnd_04.txt TLE 2036 ms 143976 KB
01_rnd_05.txt TLE 2034 ms 141344 KB
01_rnd_06.txt TLE 2034 ms 145064 KB
01_rnd_07.txt TLE 2034 ms 144304 KB
01_rnd_08.txt TLE 2034 ms 141192 KB
01_rnd_09.txt TLE 2033 ms 142156 KB
01_rnd_10.txt TLE 2035 ms 146408 KB
01_rnd_11.txt TLE 2035 ms 141348 KB
01_rnd_12.txt TLE 2035 ms 144132 KB
01_rnd_13.txt TLE 2035 ms 144180 KB
01_rnd_14.txt TLE 2033 ms 141212 KB
01_rnd_15.txt TLE 2033 ms 144536 KB
01_rnd_16.txt TLE 2034 ms 142048 KB
01_rnd_17.txt TLE 2032 ms 144788 KB
01_rnd_18.txt TLE 2034 ms 141888 KB
01_rnd_19.txt TLE 2038 ms 144072 KB
02_rndhard_00.txt TLE 2035 ms 141768 KB
02_rndhard_01.txt TLE 2034 ms 141896 KB
02_rndhard_02.txt TLE 2034 ms 144768 KB
02_rndhard_03.txt TLE 2033 ms 145972 KB
02_rndhard_04.txt TLE 2034 ms 141496 KB
02_rndhard_05.txt TLE 2033 ms 141472 KB
02_rndhard_06.txt TLE 2038 ms 141628 KB
02_rndhard_07.txt TLE 2034 ms 141536 KB
02_rndhard_08.txt TLE 2034 ms 144044 KB
02_rndhard_09.txt TLE 2033 ms 144376 KB
02_rndhard_10.txt TLE 2034 ms 143624 KB
02_rndhard_11.txt TLE 2033 ms 143880 KB
02_rndhard_12.txt TLE 2033 ms 142856 KB
02_rndhard_13.txt TLE 2034 ms 142404 KB
02_rndhard_14.txt TLE 2034 ms 143676 KB
02_rndhard_15.txt TLE 2034 ms 143592 KB
02_rndhard_16.txt TLE 2033 ms 141560 KB
02_rndhard_17.txt TLE 2034 ms 141392 KB
02_rndhard_18.txt TLE 2034 ms 141876 KB
02_rndhard_19.txt TLE 2034 ms 142620 KB
02_rndhard_20.txt TLE 2035 ms 141960 KB
02_rndhard_21.txt TLE 2033 ms 141972 KB
02_rndhard_22.txt TLE 2033 ms 143236 KB
02_rndhard_23.txt TLE 2032 ms 142612 KB
02_rndhard_24.txt TLE 2033 ms 141656 KB
02_rndhard_25.txt TLE 2035 ms 141604 KB
02_rndhard_26.txt TLE 2033 ms 142608 KB
02_rndhard_27.txt TLE 2033 ms 141368 KB
02_rndhard_28.txt TLE 2033 ms 141940 KB
02_rndhard_29.txt TLE 2033 ms 142040 KB
02_rndhard_30.txt TLE 2033 ms 141324 KB
02_rndhard_31.txt TLE 2032 ms 141444 KB
02_rndhard_32.txt TLE 2033 ms 143888 KB
02_rndhard_33.txt TLE 2033 ms 143496 KB
02_rndhard_34.txt TLE 2033 ms 141668 KB
02_rndhard_35.txt TLE 2034 ms 141672 KB
02_rndhard_36.txt TLE 2033 ms 141504 KB
02_rndhard_37.txt TLE 2034 ms 141524 KB
02_rndhard_38.txt TLE 2040 ms 142032 KB
02_rndhard_39.txt TLE 2035 ms 142784 KB
03_rndhardsmall_00.txt AC 1107 ms 48336 KB
03_rndhardsmall_01.txt AC 1105 ms 48012 KB
03_rndhardsmall_02.txt AC 1128 ms 48388 KB
03_rndhardsmall_03.txt AC 1115 ms 48380 KB
03_rndhardsmall_04.txt AC 1109 ms 47964 KB
03_rndhardsmall_05.txt AC 1102 ms 48292 KB
03_rndhardsmall_06.txt AC 1111 ms 47984 KB
03_rndhardsmall_07.txt AC 1124 ms 47944 KB
03_rndhardsmall_08.txt AC 1126 ms 48264 KB
03_rndhardsmall_09.txt AC 1101 ms 47952 KB