Submission #423535


Source Code Expand

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

object Main {

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

  type Cell = (Int,Int)

  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))
  }

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

    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.pushAll(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 1126 Byte
Status TLE
Exec Time 2036 ms
Memory 73784 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 × 70
TLE × 13
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 1097 ms 47404 KB
00_min_02.txt AC 1085 ms 47384 KB
00_min_03.txt AC 1102 ms 47412 KB
00_min_04.txt AC 1096 ms 47048 KB
00_min_05.txt AC 1089 ms 46988 KB
00_min_06.txt AC 1100 ms 47152 KB
00_min_07.txt AC 1122 ms 47212 KB
00_min_08.txt AC 1109 ms 47028 KB
00_sample_01.txt AC 1088 ms 47348 KB
00_sample_02.txt AC 1094 ms 47384 KB
00_sample_03.txt AC 1109 ms 47468 KB
00_sample_04.txt AC 1103 ms 47272 KB
00_sample_05.txt AC 1096 ms 47172 KB
01_rnd_00.txt AC 1215 ms 52916 KB
01_rnd_01.txt TLE 2033 ms 68656 KB
01_rnd_02.txt TLE 2034 ms 70652 KB
01_rnd_03.txt TLE 2035 ms 68292 KB
01_rnd_04.txt TLE 2033 ms 68256 KB
01_rnd_05.txt AC 1222 ms 53452 KB
01_rnd_06.txt AC 1795 ms 61156 KB
01_rnd_07.txt TLE 2033 ms 69100 KB
01_rnd_08.txt AC 1208 ms 52620 KB
01_rnd_09.txt AC 1226 ms 53040 KB
01_rnd_10.txt TLE 2033 ms 72148 KB
01_rnd_11.txt AC 1232 ms 52868 KB
01_rnd_12.txt TLE 2032 ms 69500 KB
01_rnd_13.txt TLE 2035 ms 69700 KB
01_rnd_14.txt AC 1561 ms 53284 KB
01_rnd_15.txt TLE 2036 ms 68044 KB
01_rnd_16.txt AC 1192 ms 52696 KB
01_rnd_17.txt TLE 2034 ms 73784 KB
01_rnd_18.txt AC 1208 ms 53084 KB
01_rnd_19.txt TLE 2034 ms 71744 KB
02_rndhard_00.txt AC 1443 ms 57048 KB
02_rndhard_01.txt AC 1455 ms 56712 KB
02_rndhard_02.txt TLE 2035 ms 63468 KB
02_rndhard_03.txt TLE 2033 ms 62516 KB
02_rndhard_04.txt AC 1230 ms 52852 KB
02_rndhard_05.txt AC 1249 ms 53016 KB
02_rndhard_06.txt AC 1388 ms 55512 KB
02_rndhard_07.txt AC 1259 ms 53232 KB
02_rndhard_08.txt AC 1871 ms 61716 KB
02_rndhard_09.txt AC 1780 ms 61116 KB
02_rndhard_10.txt AC 1826 ms 65860 KB
02_rndhard_11.txt AC 1846 ms 63432 KB
02_rndhard_12.txt AC 1691 ms 60328 KB
02_rndhard_13.txt AC 1685 ms 60096 KB
02_rndhard_14.txt AC 1894 ms 66352 KB
02_rndhard_15.txt AC 1854 ms 66364 KB
02_rndhard_16.txt AC 1377 ms 54924 KB
02_rndhard_17.txt AC 1378 ms 54820 KB
02_rndhard_18.txt AC 1465 ms 56880 KB
02_rndhard_19.txt AC 1416 ms 57212 KB
02_rndhard_20.txt AC 1431 ms 57336 KB
02_rndhard_21.txt AC 1475 ms 57064 KB
02_rndhard_22.txt AC 1785 ms 61496 KB
02_rndhard_23.txt AC 1638 ms 59888 KB
02_rndhard_24.txt AC 1406 ms 55152 KB
02_rndhard_25.txt AC 1381 ms 55132 KB
02_rndhard_26.txt AC 1448 ms 57436 KB
02_rndhard_27.txt AC 1314 ms 53336 KB
02_rndhard_28.txt AC 1482 ms 57228 KB
02_rndhard_29.txt AC 1527 ms 57248 KB
02_rndhard_30.txt AC 1203 ms 53308 KB
02_rndhard_31.txt AC 1211 ms 53260 KB
02_rndhard_32.txt AC 1698 ms 60448 KB
02_rndhard_33.txt AC 1659 ms 60196 KB
02_rndhard_34.txt AC 1401 ms 54980 KB
02_rndhard_35.txt AC 1380 ms 55072 KB
02_rndhard_36.txt AC 1333 ms 54224 KB
02_rndhard_37.txt AC 1341 ms 54228 KB
02_rndhard_38.txt AC 1521 ms 56864 KB
02_rndhard_39.txt AC 1521 ms 57180 KB
03_rndhardsmall_00.txt AC 1115 ms 47084 KB
03_rndhardsmall_01.txt AC 1092 ms 46916 KB
03_rndhardsmall_02.txt AC 1094 ms 47004 KB
03_rndhardsmall_03.txt AC 1108 ms 47160 KB
03_rndhardsmall_04.txt AC 1158 ms 47312 KB
03_rndhardsmall_05.txt AC 1101 ms 47120 KB
03_rndhardsmall_06.txt AC 1096 ms 47300 KB
03_rndhardsmall_07.txt AC 1102 ms 47388 KB
03_rndhardsmall_08.txt AC 1104 ms 47336 KB
03_rndhardsmall_09.txt AC 1085 ms 47116 KB