Submission #421380
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 | 2037 ms |
Memory | 87188 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 | 1218 ms | 48128 KB |
00_min_02.txt | AC | 1134 ms | 48204 KB |
00_min_03.txt | AC | 1138 ms | 48404 KB |
00_min_04.txt | AC | 1132 ms | 48284 KB |
00_min_05.txt | AC | 1129 ms | 48252 KB |
00_min_06.txt | AC | 1134 ms | 48244 KB |
00_min_07.txt | AC | 1137 ms | 48308 KB |
00_min_08.txt | AC | 1133 ms | 47920 KB |
00_sample_01.txt | AC | 1137 ms | 48236 KB |
00_sample_02.txt | AC | 1157 ms | 48300 KB |
00_sample_03.txt | AC | 1231 ms | 48236 KB |
00_sample_04.txt | AC | 1158 ms | 48300 KB |
00_sample_05.txt | AC | 1146 ms | 48256 KB |
01_rnd_00.txt | AC | 1505 ms | 69148 KB |
01_rnd_01.txt | TLE | 2037 ms | 86944 KB |
01_rnd_02.txt | AC | 1832 ms | 74024 KB |
01_rnd_03.txt | TLE | 2037 ms | 80544 KB |
01_rnd_04.txt | TLE | 2036 ms | 86472 KB |
01_rnd_05.txt | AC | 1522 ms | 68648 KB |
01_rnd_06.txt | AC | 1813 ms | 70816 KB |
01_rnd_07.txt | AC | 1830 ms | 71736 KB |
01_rnd_08.txt | AC | 1503 ms | 67908 KB |
01_rnd_09.txt | AC | 1529 ms | 68348 KB |
01_rnd_10.txt | AC | 1900 ms | 71364 KB |
01_rnd_11.txt | AC | 1521 ms | 69376 KB |
01_rnd_12.txt | TLE | 2035 ms | 84980 KB |
01_rnd_13.txt | AC | 1949 ms | 80580 KB |
01_rnd_14.txt | AC | 1503 ms | 68336 KB |
01_rnd_15.txt | AC | 1905 ms | 72928 KB |
01_rnd_16.txt | AC | 1533 ms | 69512 KB |
01_rnd_17.txt | AC | 1923 ms | 73132 KB |
01_rnd_18.txt | AC | 1492 ms | 68204 KB |
01_rnd_19.txt | TLE | 2036 ms | 87188 KB |
02_rndhard_00.txt | AC | 1603 ms | 68736 KB |
02_rndhard_01.txt | AC | 1636 ms | 69668 KB |
02_rndhard_02.txt | AC | 1856 ms | 70668 KB |
02_rndhard_03.txt | AC | 1825 ms | 70728 KB |
02_rndhard_04.txt | AC | 1519 ms | 68440 KB |
02_rndhard_05.txt | AC | 1511 ms | 68876 KB |
02_rndhard_06.txt | AC | 1558 ms | 68552 KB |
02_rndhard_07.txt | AC | 1516 ms | 69580 KB |
02_rndhard_08.txt | AC | 1765 ms | 69804 KB |
02_rndhard_09.txt | AC | 1742 ms | 69804 KB |
02_rndhard_10.txt | AC | 1747 ms | 70012 KB |
02_rndhard_11.txt | AC | 1747 ms | 69264 KB |
02_rndhard_12.txt | AC | 1667 ms | 68924 KB |
02_rndhard_13.txt | AC | 1671 ms | 69476 KB |
02_rndhard_14.txt | AC | 1825 ms | 69844 KB |
02_rndhard_15.txt | AC | 1796 ms | 70028 KB |
02_rndhard_16.txt | AC | 1570 ms | 68452 KB |
02_rndhard_17.txt | AC | 1557 ms | 68788 KB |
02_rndhard_18.txt | AC | 1620 ms | 69908 KB |
02_rndhard_19.txt | AC | 1602 ms | 68664 KB |
02_rndhard_20.txt | AC | 1600 ms | 70296 KB |
02_rndhard_21.txt | AC | 1594 ms | 70044 KB |
02_rndhard_22.txt | AC | 1745 ms | 69644 KB |
02_rndhard_23.txt | AC | 1693 ms | 69960 KB |
02_rndhard_24.txt | AC | 1602 ms | 69876 KB |
02_rndhard_25.txt | AC | 1594 ms | 70008 KB |
02_rndhard_26.txt | AC | 1591 ms | 68816 KB |
02_rndhard_27.txt | AC | 1533 ms | 69608 KB |
02_rndhard_28.txt | AC | 1625 ms | 68900 KB |
02_rndhard_29.txt | AC | 1691 ms | 70044 KB |
02_rndhard_30.txt | AC | 1523 ms | 68388 KB |
02_rndhard_31.txt | AC | 1540 ms | 68284 KB |
02_rndhard_32.txt | AC | 1706 ms | 69948 KB |
02_rndhard_33.txt | AC | 1666 ms | 68724 KB |
02_rndhard_34.txt | AC | 1559 ms | 68772 KB |
02_rndhard_35.txt | AC | 1566 ms | 68384 KB |
02_rndhard_36.txt | AC | 1559 ms | 69760 KB |
02_rndhard_37.txt | AC | 1554 ms | 69228 KB |
02_rndhard_38.txt | AC | 1608 ms | 68624 KB |
02_rndhard_39.txt | AC | 1618 ms | 69760 KB |
03_rndhardsmall_00.txt | AC | 1164 ms | 48284 KB |
03_rndhardsmall_01.txt | AC | 1160 ms | 48116 KB |
03_rndhardsmall_02.txt | AC | 1156 ms | 48340 KB |
03_rndhardsmall_03.txt | AC | 1170 ms | 47792 KB |
03_rndhardsmall_04.txt | AC | 1167 ms | 48260 KB |
03_rndhardsmall_05.txt | AC | 1186 ms | 48196 KB |
03_rndhardsmall_06.txt | AC | 1162 ms | 48224 KB |
03_rndhardsmall_07.txt | AC | 1161 ms | 48228 KB |
03_rndhardsmall_08.txt | AC | 1158 ms | 48252 KB |
03_rndhardsmall_09.txt | AC | 1165 ms | 48324 KB |