結果

問題 No.367 ナイトの転身
ユーザー scaler
提出日時 2024-09-01 11:29:11
言語 Scala(Beta)
(3.6.2)
結果
TLE  
実行時間 -
コード長 1,391 bytes
コンパイル時間 14,465 ms
コンパイル使用メモリ 270,584 KB
実行使用メモリ 90,620 KB
最終ジャッジ日時 2024-09-01 11:29:45
合計ジャッジ時間 33,457 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 10 TLE * 2 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #

import scala.collection.mutable.PriorityQueue
import scala.io.StdIn.readLine

def unless(condition: Boolean)(block: => Unit): Unit =
  if !condition then block

@main
def yuki367(): Unit =
  
  val dx: Seq[Int] = Seq(1, 1,-1,-1, 1, 1, 2, 2,-1,-1,-2,-2)
  val dy: Seq[Int] = Seq(1,-1,-1, 1, 2,-2, 1,-1, 2,-2, 1,-1)

  val f: Array[Array[Array[Int]]] = Array.ofDim[Int](512, 512, 2)
  for
    i <- 0 until 512
    j <- 0 until 512
    k <- 0 until 2
  do
    f(i)(j)(k) = -1111111
  
  val Array(h, w) = readLine.split(" ").map(_.toInt)
  val s: Array[String] = Array.ofDim[String](h)
  var ans: Int = 0
  for
    i <- 0 until h
  do
    s(i) = readLine
  
  val pq: PriorityQueue[(Int, Int, Int, Int)] = PriorityQueue()
  for
    i <- 0 until h
    j <- 0 until w
    if s(i)(j) == 'S'
  do
    pq.enqueue((0, i, j, 0))

  while pq.nonEmpty do
    var (c, x, y, t) = pq.dequeue
    unless((x < 0 || h <= x || y < 0 || w <= y) || (f(x)(y)(t) >= c)) {
      f(x)(y)(t) = c
      if s(x)(y) == 'R' then
        t = 1 - t
      if t != 0 then
        for i <- 0 until 4 do
          pq.enqueue((c - 1, x + dx(i), y + dy(i), t)) 
      else
        for i <- 0 until 8 do
          pq.enqueue((c - 1, x + dx(i + 4), y + dy(i + 4), t))
    }
  for
    i <- 0 until h
    j <- 0 until w
    if s(i)(j) == 'G'
  do
    ans = -f(i)(j).max
  if ans > 1000000 then
    println(-1)
  else
    println(ans)
0