Submission #144456


Source Code Expand

Copy
import java.util.Scanner
import java.io.PrintWriter
import java.util.concurrent.ArrayBlockingQueue
import scala.collection.mutable

/**
 * Created by hama_du on 2014/03/15.
 */
object Main extends App {
  val INF = 10000000
  val dx = Array(1, 0, -1, 0)
  val dy = Array(0, 1, 0, -1)

  val in = new Scanner(System.in)
  val out = new PrintWriter(System.out)

  val R,C,K = in.nextInt()
  in.nextLine()
  val map = Array.ofDim[Char](R,C)
  var startY = 0
  var startX = 0
  var compY = 0
  var compX = 0
  var goalY = 0
  var goalX = 0
  for (i <- 0 until R) {
    map(i) = in.nextLine().toCharArray
    for (j <- 0 until C) {
      if (map(i)(j) == 'S') {
        startY = i
        startX = j
      } else if (map(i)(j) == 'C') {
        compY = i
        compX = j
      } else if (map(i)(j) == 'G') {
        goalY = i
        goalX = j
      }
    }
  }

  val fromStart = go(startY, startX, compY, compX)
  val fromGoal = go(goalY, goalX, compY, compX)
  val fromComp = go(compY, compX, compY, compX)


  var answer = INF
  for (sk <- 0 to K) {
    val gk = K - sk
    val startToGoal = fromStart(goalY)(goalX)(sk)
    for (i <- 0 until R) {
      for (j <- 0 until C) {
        val foe = fromStart(i)(j)(sk) + fromGoal(i)(j)(sk)
        if (foe <= startToGoal) {
          val path = startToGoal + fromComp(i)(j)(gk) * 2
          answer = answer min path
        }
      }
    }
  }

  if (answer >= INF) {
    answer = -1
  }
  out.println(answer)
  out.flush()


  def go(fy: Int, fx: Int, py: Int, px: Int) = {
    val dp = Array.ofDim[Int](R,C,K+1)
    for (i <- 0 until R) {
      for (j <- 0 until C) {
        dp(i)(j) = Array.fill[Int](K+1)(INF)
      }
    }

    dp(fy)(fx)(0) = 0
    val queue = new mutable.Queue[(Int,Int,Int,Int)]()
    queue += ((fy, fx, 0, 0))
    while (queue.size >= 1) {
      val stat = queue.dequeue()
      (0 until 4).foreach(d => {
        val toy = stat._1 + dy(d)
        val tox = stat._2 + dx(d)
        if (isValid(toy, tox)) {
          val top = {
            if (toy == py && tox == px) {
              1
            } else {
              stat._1
            }
          }
          val tok = stat._3 + {
            if (map(toy)(tox) == 'E') {
              1
            } else {
              0
            }
          }
          if (tok <= K) {
            val tt = stat._4 + 1
            if (dp(toy)(tox)(tok) > tt) {
              dp(toy)(tox)(tok) = tt
              queue += ((toy, tox, tok, tt))
            }
          }
        }
      })
    }
    for (i <- 0 until R) {
      for (j <- 0 until C) {
        for (k <- 0 until K) {
          dp(i)(j)(k+1) = dp(i)(j)(k+1) min dp(i)(j)(k)
        }
      }
    }
    dp
  }

  def isValid(y: Int, x: Int): Boolean = {
    return (0 <= x && x < C && 0 <= y && y < R && map(y)(x) != 'T')
  }


}

Submission Info

Submission Time
Task C - 最後の森
User hamadu
Language Scala (2.9.1)
Score 0
Code Size 2938 Byte
Status
Exec Time 1617 ms
Memory 68064 KB

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 100 case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, case_22.txt, case_23.txt, case_24.txt, case_25.txt, case_26.txt, case_27.txt, case_28.txt, case_29.txt, case_30.txt
Case Name Status Exec Time Memory
case_01.txt 1157 ms 44348 KB
case_02.txt 1100 ms 44352 KB
case_03.txt 1099 ms 44368 KB
case_04.txt 1110 ms 44428 KB
case_05.txt 1094 ms 44392 KB
case_06.txt 1123 ms 44468 KB
case_07.txt 1160 ms 44908 KB
case_08.txt 1334 ms 52288 KB
case_09.txt 1243 ms 47116 KB
case_10.txt 1323 ms 48488 KB
case_11.txt 1275 ms 49520 KB
case_12.txt 1141 ms 44552 KB
case_13.txt 1376 ms 55272 KB
case_14.txt 1611 ms 68064 KB
case_15.txt 1541 ms 67160 KB
case_16.txt 1462 ms 56292 KB
case_17.txt 1568 ms 67148 KB
case_18.txt 1321 ms 49080 KB
case_19.txt 1492 ms 61448 KB
case_20.txt 1414 ms 58412 KB
case_21.txt 1569 ms 67648 KB
case_22.txt 1355 ms 55252 KB
case_23.txt 1617 ms 67560 KB
case_24.txt 1464 ms 57596 KB
case_25.txt 1556 ms 64568 KB
case_26.txt 1391 ms 56560 KB
case_27.txt 1438 ms 59600 KB
case_28.txt 1552 ms 64444 KB
case_29.txt 1326 ms 49152 KB
case_30.txt 1380 ms 55296 KB
sample_01.txt 1106 ms 44420 KB
sample_02.txt 1114 ms 44320 KB
sample_03.txt 1155 ms 44444 KB
sample_04.txt 1181 ms 44772 KB