Submission #421377

---

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

Judge Result