結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー norioc
提出日時 2015-09-14 22:23:20
言語 Scala(Beta)
(3.6.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,104 bytes
コンパイル時間 6,645 ms
コンパイル使用メモリ 232,044 KB
最終ジャッジ日時 2024-11-14 19:11:58
合計ジャッジ時間 7,073 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
-- [E040] Syntax Error: Main.scala:59:32 ---------------------------------------
59 |  def main(args: Array[String]) {
   |                                ^
   |                                '=' expected, but '{' found
1 error found

ソースコード

diff #
raw source code 

import scala.collection.mutable.PriorityQueue
import scala.collection.mutable.HashSet
import scala.math._

object Main {
  def Ord = new Ordering[(Int, Int, Int)] { // (row, col, cost)
    def compare(a: (Int, Int, Int), b: (Int, Int, Int)): Int =
      b._3.compare(a._3)
  }

  def dijkstra(start: (Int, Int), goal: (Int, Int), g: Array[Array[Int]]): Int = {
    val N = g.size
    val q = new PriorityQueue[(Int, Int, Int)]()(Ord) // (row, col, cost)
    q.enqueue((start._1, start._2, 0))

    val used = new HashSet[(Int, Int)]
    while (!q.isEmpty) {
      val (row, col, cost) = q.dequeue

      if (row == goal._1 && col == goal._2) return cost

      if (!used.contains((row, col))) {
        used.add((row, col))
        for (i <- -1 to 1; j <- -1 to 1 if abs(i) + abs(j) == 1) {
          val r = row + i
          val c = col + j
          if (0 <= r && r < N && 0 <= c && c < N) {
            q.enqueue((r, c, cost + g(r)(c)))
          }
        }
      }
    }

    assert(false, "can not reach goal")
    return 0
  }

  def calc(n: Int, vitality: Int, oasis: (Int, Int), g: Array[Array[Int]]): Boolean = {
    // オアシス経由せずにいける
    if (vitality > dijkstra((0, 0), (n-1, n-1), g)) {
      return true
    }

    // オアシスは存在しない
    if (oasis._1 == -1 && oasis._2 == -1) return false

    // オアシス経由する
    val a = dijkstra((0, 0), oasis, g) // スタートからオアシスまでのコスト
    if (vitality > a) { // オアシスまでたどり着ける
      val v = (vitality - a) * 2 // 体力回復

      if (v > dijkstra(oasis, (n-1, n-1), g)) { // オアシスからゴールにたどり着ける
        return true
      }
    }
    return false
  }

  def main(args: Array[String]) {
    val sc = new java.util.Scanner(System.in)
    val n, v, ox, oy = sc.nextInt
    val g = Array.ofDim[Int](n, n)
    for (i <- 0 to n-1) {
      for (j <- 0 to n-1) {
        g(i)(j) = sc.nextInt
      }
    }

    val reachable = calc(n, v, (oy-1, ox-1), g)
    if (reachable)
      println("YES")
    else
      println("NO")
  }
}
0