Submission #144902


Source Code Expand

Copy
import java.util.Scanner
import java.io.PrintWriter
import scala.collection.mutable
import scala.util.control.Breaks
 
/**
 * 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)
  val fromGoal = go(goalY, goalX)
  val fromComp = go(compY, compX)
 
  var answer = INF
  for (i <- 0 until R) {
    for (j <- 0 until C) {
      for (sk <- 0 to K) {
        for (sk1 <- 0 to sk) {
          var sk2 = sk - sk1
          var gk = K - sk
          if (map(i)(j) == 'E') {
            sk2 += 1
            gk += 1
          }
          val path = fromStart(i)(j)(sk1) + fromGoal(i)(j)(sk2) + 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) = {
    val dp = Array.ofDim[Int](R,C,K+2)
    for (i <- 0 until R) {
      for (j <- 0 until C) {
        dp(i)(j) = Array.fill[Int](K+2)(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 tok = stat._3 + {
            if (map(toy)(tox) == 'E') {
              1
            } else {
              0
            }
          }
          if (tok <= K+1) {
            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+1) {
          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 100
Code Size 2764 Byte
Status
Exec Time 1997 ms
Memory 73820 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 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 1083 ms 44372 KB
case_02.txt 1031 ms 44536 KB
case_03.txt 1015 ms 44536 KB
case_04.txt 1024 ms 44376 KB
case_05.txt 1021 ms 44416 KB
case_06.txt 1047 ms 44640 KB
case_07.txt 1127 ms 45576 KB
case_08.txt 1367 ms 55936 KB
case_09.txt 1248 ms 48488 KB
case_10.txt 1236 ms 49640 KB
case_11.txt 1285 ms 49912 KB
case_12.txt 1083 ms 44808 KB
case_13.txt 1373 ms 55304 KB
case_14.txt 1992 ms 68236 KB
case_15.txt 1958 ms 73668 KB
case_16.txt 1445 ms 58316 KB
case_17.txt 1997 ms 67532 KB
case_18.txt 1318 ms 51140 KB
case_19.txt 1664 ms 61588 KB
case_20.txt 1724 ms 59776 KB
case_21.txt 1982 ms 73820 KB
case_22.txt 1355 ms 56504 KB
case_23.txt 1931 ms 67516 KB
case_24.txt 1445 ms 57016 KB
case_25.txt 1820 ms 64856 KB
case_26.txt 1438 ms 57924 KB
case_27.txt 1736 ms 61620 KB
case_28.txt 1795 ms 65024 KB
case_29.txt 1341 ms 51148 KB
case_30.txt 1435 ms 56128 KB
sample_01.txt 1071 ms 44548 KB
sample_02.txt 1058 ms 44540 KB
sample_03.txt 1049 ms 44548 KB
sample_04.txt 1164 ms 45436 KB