Submission #421379
Source Code Expand
import java.util.Scanner object Main { val dx = Array(-1, 1, 0, 0) val dy = Array(0, 0, 1, -1) def main(args: Array[String]): Unit = { val scanner = new java.util.Scanner(System.in) val h = scanner.nextInt() val w = scanner.nextInt() val board = (1 to h).map { _ => scanner.next().toCharArray }.toArray val result = if (solve(h, w, board)) "Yes" else "No" println(result) } def solve(h: Int, w: Int, board: Array[Array[Char]]): Boolean = { val start = (for { i <- (0 until h) j <- (0 until w) } yield (i, j)).find { case (i, j) => board(i)(j) == 's' } search(start.get, h, w, board) } def search( s: (Int, Int), h: Int, w: Int, board: Array[Array[Char]]): Boolean = { // val visited = scala.collection.mutable.Set.empty[(Int, Int)] var visited = Array.fill(h)(Array.fill(w)(false)) var stack = List(s) while (stack.nonEmpty) { stack match { case Nil => return false case current :: t => stack = t current match { case (i, j) if i < 0 || i >= h || j < 0 || j >= w => // case (i, j) if visited((i, j)) => case (i, j) if visited(i)(j) => case (i, j) if board(i)(j) == '#' => case (i, j) if board(i)(j) == 'g' => return true case (i, j) => // visited += ((i, j)) visited(i)(j) = true; val news = (0 to 3).map { x => (i + dy(x), j + dx(x)) }.toList stack = news ::: stack } } } false } }
Submission Info
Submission Time | |
---|---|
Task | A - 深さ優先探索 |
User | yoshikyoto |
Language | Scala (2.11.5) |
Score | 0 |
Code Size | 1665 Byte |
Status | TLE |
Exec Time | 2036 ms |
Memory | 87440 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
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 | 1192 ms | 48188 KB |
00_min_02.txt | AC | 1166 ms | 48332 KB |
00_min_03.txt | AC | 1154 ms | 48516 KB |
00_min_04.txt | AC | 1161 ms | 48416 KB |
00_min_05.txt | AC | 1174 ms | 48228 KB |
00_min_06.txt | AC | 1168 ms | 48408 KB |
00_min_07.txt | AC | 1149 ms | 48360 KB |
00_min_08.txt | AC | 1132 ms | 48340 KB |
00_sample_01.txt | AC | 1145 ms | 48304 KB |
00_sample_02.txt | AC | 1149 ms | 48044 KB |
00_sample_03.txt | AC | 1162 ms | 48440 KB |
00_sample_04.txt | AC | 1167 ms | 48428 KB |
00_sample_05.txt | AC | 1158 ms | 48032 KB |
01_rnd_00.txt | AC | 1542 ms | 69240 KB |
01_rnd_01.txt | TLE | 2033 ms | 87440 KB |
01_rnd_02.txt | AC | 1905 ms | 74128 KB |
01_rnd_03.txt | TLE | 2036 ms | 80928 KB |
01_rnd_04.txt | TLE | 2035 ms | 86740 KB |
01_rnd_05.txt | AC | 1495 ms | 69000 KB |
01_rnd_06.txt | AC | 1832 ms | 71100 KB |
01_rnd_07.txt | AC | 1804 ms | 72444 KB |
01_rnd_08.txt | AC | 1511 ms | 69308 KB |
01_rnd_09.txt | AC | 1618 ms | 68856 KB |
01_rnd_10.txt | AC | 1872 ms | 72040 KB |
01_rnd_11.txt | AC | 1530 ms | 69756 KB |
01_rnd_12.txt | TLE | 2034 ms | 84768 KB |
01_rnd_13.txt | AC | 1936 ms | 81560 KB |
01_rnd_14.txt | AC | 1500 ms | 69748 KB |
01_rnd_15.txt | AC | 1869 ms | 72728 KB |
01_rnd_16.txt | AC | 1527 ms | 68312 KB |
01_rnd_17.txt | AC | 1908 ms | 73120 KB |
01_rnd_18.txt | AC | 1492 ms | 67904 KB |
01_rnd_19.txt | TLE | 2035 ms | 86368 KB |
02_rndhard_00.txt | AC | 1597 ms | 68532 KB |
02_rndhard_01.txt | AC | 1615 ms | 68704 KB |
02_rndhard_02.txt | AC | 1829 ms | 71160 KB |
02_rndhard_03.txt | AC | 1798 ms | 70944 KB |
02_rndhard_04.txt | AC | 1530 ms | 68188 KB |
02_rndhard_05.txt | AC | 1515 ms | 69400 KB |
02_rndhard_06.txt | AC | 1532 ms | 68792 KB |
02_rndhard_07.txt | AC | 1520 ms | 68792 KB |
02_rndhard_08.txt | AC | 1729 ms | 70196 KB |
02_rndhard_09.txt | AC | 1758 ms | 69756 KB |
02_rndhard_10.txt | AC | 1739 ms | 69444 KB |
02_rndhard_11.txt | AC | 1751 ms | 70032 KB |
02_rndhard_12.txt | AC | 1730 ms | 68804 KB |
02_rndhard_13.txt | AC | 1704 ms | 69880 KB |
02_rndhard_14.txt | AC | 1734 ms | 69992 KB |
02_rndhard_15.txt | AC | 1772 ms | 69748 KB |
02_rndhard_16.txt | AC | 1570 ms | 68044 KB |
02_rndhard_17.txt | AC | 1549 ms | 68896 KB |
02_rndhard_18.txt | AC | 1623 ms | 69820 KB |
02_rndhard_19.txt | AC | 1580 ms | 68568 KB |
02_rndhard_20.txt | AC | 1620 ms | 69880 KB |
02_rndhard_21.txt | AC | 1562 ms | 69068 KB |
02_rndhard_22.txt | AC | 1729 ms | 70084 KB |
02_rndhard_23.txt | AC | 1625 ms | 68872 KB |
02_rndhard_24.txt | AC | 1539 ms | 68932 KB |
02_rndhard_25.txt | AC | 1546 ms | 68644 KB |
02_rndhard_26.txt | AC | 1605 ms | 68600 KB |
02_rndhard_27.txt | AC | 1521 ms | 69748 KB |
02_rndhard_28.txt | AC | 1635 ms | 69860 KB |
02_rndhard_29.txt | AC | 1637 ms | 70396 KB |
02_rndhard_30.txt | AC | 1515 ms | 69780 KB |
02_rndhard_31.txt | AC | 1501 ms | 68732 KB |
02_rndhard_32.txt | AC | 1716 ms | 68924 KB |
02_rndhard_33.txt | AC | 1651 ms | 68896 KB |
02_rndhard_34.txt | AC | 1554 ms | 68864 KB |
02_rndhard_35.txt | AC | 1551 ms | 68772 KB |
02_rndhard_36.txt | AC | 1579 ms | 68560 KB |
02_rndhard_37.txt | AC | 1551 ms | 68672 KB |
02_rndhard_38.txt | AC | 1593 ms | 69876 KB |
02_rndhard_39.txt | AC | 1613 ms | 68748 KB |
03_rndhardsmall_00.txt | AC | 1154 ms | 48448 KB |
03_rndhardsmall_01.txt | AC | 1154 ms | 48224 KB |
03_rndhardsmall_02.txt | AC | 1190 ms | 48392 KB |
03_rndhardsmall_03.txt | AC | 1184 ms | 48440 KB |
03_rndhardsmall_04.txt | AC | 1162 ms | 48352 KB |
03_rndhardsmall_05.txt | AC | 1154 ms | 48324 KB |
03_rndhardsmall_06.txt | AC | 1170 ms | 48152 KB |
03_rndhardsmall_07.txt | AC | 1193 ms | 48428 KB |
03_rndhardsmall_08.txt | AC | 1180 ms | 48368 KB |
03_rndhardsmall_09.txt | AC | 1144 ms | 48380 KB |