Submission #423511


Source Code Expand

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

object Main {

  val Array(h,w,_*) = readLine.split(" ").map(_.toInt)
  val grid = (for(i <- 0 until h) yield readLine).toArray

  type Cell = (Int,Int)

  @tailrec
  def dfs(stk: Stack[Cell], used: Set[Cell] = Set.empty[Cell]): Boolean = {

    def next(now: Cell, used: Set[Cell]): List[Cell] = {
      List((0,-1), (1,0), (0,1), (-1,0))
      .flatMap{case (dx:Int, dy:Int) => List((now._1 + dx, now._2 + dy))}
      .filter((d:Cell) => 0 <= d._1 && 0 <= d._2 && d._1 < w && d._2 < h)
      .filter((d:Cell) => grid(d._2)(d._1)!='#' && !used.contains(d))
    }

    val (now, res) = stk.pop2

    if(grid(now._2)(now._1)=='g') true
    else {
      val nx = next(now,used)
      if(res.size + nx.size == 0) false
      else dfs(res ++ nx, used + now)
    }
  }

  def main (args: Array[String]): Unit = {
    val res = for{
      sy <- 0 until h
      sx <- 0 until w
      if(grid(sy)(sx)=='s')
    } yield dfs(Stack((sx,sy)))

    println(if(res.fold(false)(_ | _))"Yes" else "No")
  }
}

Submission Info

Submission Time
Task A - 深さ優先探索
User TobiasGSmollett
Language Scala (2.11.5)
Score 0
Code Size 1104 Byte
Status TLE
Exec Time 2042 ms
Memory 64880 KB

Compile Error

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 5
AC × 37
TLE × 46
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 AC 1146 ms 47452 KB
00_min_02.txt AC 1109 ms 47416 KB
00_min_03.txt AC 1102 ms 47336 KB
00_min_04.txt AC 1106 ms 47492 KB
00_min_05.txt AC 1125 ms 47628 KB
00_min_06.txt AC 1103 ms 47564 KB
00_min_07.txt AC 1087 ms 47176 KB
00_min_08.txt AC 1108 ms 47580 KB
00_sample_01.txt AC 1149 ms 47472 KB
00_sample_02.txt AC 1151 ms 47620 KB
00_sample_03.txt AC 1153 ms 47288 KB
00_sample_04.txt AC 1150 ms 47208 KB
00_sample_05.txt AC 1111 ms 47492 KB
01_rnd_00.txt AC 1208 ms 53156 KB
01_rnd_01.txt TLE 2038 ms 63208 KB
01_rnd_02.txt TLE 2035 ms 60884 KB
01_rnd_03.txt TLE 2036 ms 62936 KB
01_rnd_04.txt TLE 2034 ms 64880 KB
01_rnd_05.txt AC 1243 ms 53628 KB
01_rnd_06.txt TLE 2033 ms 62332 KB
01_rnd_07.txt TLE 2040 ms 62712 KB
01_rnd_08.txt AC 1203 ms 52680 KB
01_rnd_09.txt AC 1214 ms 53668 KB
01_rnd_10.txt TLE 2035 ms 62640 KB
01_rnd_11.txt AC 1236 ms 53128 KB
01_rnd_12.txt TLE 2035 ms 62704 KB
01_rnd_13.txt TLE 2035 ms 61820 KB
01_rnd_14.txt AC 1489 ms 52788 KB
01_rnd_15.txt TLE 2035 ms 61508 KB
01_rnd_16.txt AC 1225 ms 52936 KB
01_rnd_17.txt TLE 2034 ms 63228 KB
01_rnd_18.txt AC 1224 ms 53076 KB
01_rnd_19.txt TLE 2036 ms 62164 KB
02_rndhard_00.txt TLE 2036 ms 62820 KB
02_rndhard_01.txt TLE 2033 ms 62024 KB
02_rndhard_02.txt TLE 2035 ms 62996 KB
02_rndhard_03.txt TLE 2034 ms 62224 KB
02_rndhard_04.txt AC 1424 ms 57336 KB
02_rndhard_05.txt AC 1450 ms 56844 KB
02_rndhard_06.txt TLE 2034 ms 63456 KB
02_rndhard_07.txt AC 1317 ms 53432 KB
02_rndhard_08.txt TLE 2034 ms 61904 KB
02_rndhard_09.txt TLE 2034 ms 62936 KB
02_rndhard_10.txt TLE 2042 ms 60916 KB
02_rndhard_11.txt TLE 2034 ms 60616 KB
02_rndhard_12.txt TLE 2034 ms 61584 KB
02_rndhard_13.txt TLE 2034 ms 61164 KB
02_rndhard_14.txt TLE 2035 ms 62996 KB
02_rndhard_15.txt TLE 2034 ms 63840 KB
02_rndhard_16.txt TLE 2037 ms 61100 KB
02_rndhard_17.txt TLE 2035 ms 61536 KB
02_rndhard_18.txt TLE 2032 ms 63600 KB
02_rndhard_19.txt TLE 2034 ms 62636 KB
02_rndhard_20.txt TLE 2042 ms 61852 KB
02_rndhard_21.txt TLE 2033 ms 61960 KB
02_rndhard_22.txt TLE 2034 ms 61700 KB
02_rndhard_23.txt TLE 2034 ms 61848 KB
02_rndhard_24.txt TLE 2034 ms 63632 KB
02_rndhard_25.txt TLE 2034 ms 61976 KB
02_rndhard_26.txt TLE 2034 ms 62748 KB
02_rndhard_27.txt AC 1516 ms 57060 KB
02_rndhard_28.txt TLE 2034 ms 61828 KB
02_rndhard_29.txt TLE 2035 ms 63164 KB
02_rndhard_30.txt AC 1361 ms 54856 KB
02_rndhard_31.txt AC 1352 ms 54264 KB
02_rndhard_32.txt TLE 2034 ms 62512 KB
02_rndhard_33.txt TLE 2033 ms 62184 KB
02_rndhard_34.txt TLE 2034 ms 63008 KB
02_rndhard_35.txt TLE 2033 ms 62644 KB
02_rndhard_36.txt TLE 2034 ms 61200 KB
02_rndhard_37.txt TLE 2034 ms 61224 KB
02_rndhard_38.txt TLE 2033 ms 63092 KB
02_rndhard_39.txt TLE 2035 ms 63368 KB
03_rndhardsmall_00.txt AC 1132 ms 47480 KB
03_rndhardsmall_01.txt AC 1137 ms 47580 KB
03_rndhardsmall_02.txt AC 1144 ms 47524 KB
03_rndhardsmall_03.txt AC 1135 ms 47532 KB
03_rndhardsmall_04.txt AC 1279 ms 47436 KB
03_rndhardsmall_05.txt AC 1181 ms 47044 KB
03_rndhardsmall_06.txt AC 1108 ms 47408 KB
03_rndhardsmall_07.txt AC 1117 ms 47516 KB
03_rndhardsmall_08.txt AC 1121 ms 47628 KB
03_rndhardsmall_09.txt AC 1083 ms 47164 KB