Submission #144626


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)
  val fromGoal = go(goalY, goalX)
  val fromComp = go(compY, compX)


  var answer = INF
  for (sk <- 0 to K) {
    val startToGoal = fromStart(goalY)(goalX)(sk)
    for (i <- 0 until R) {
      for (j <- 0 until C) {
        for (sk1 <- 0 to sk) {
          var sk2 = sk - sk1
          var gk = K - sk
          if (map(i)(j) == 'E') {
            sk2 += 1
            gk += 1
          }
          val foe = fromStart(i)(j)(sk1) + fromGoal(i)(j)(sk2)
          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) = {
    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 0
Code Size 2908 Byte
Status
Exec Time 1992 ms
Memory 76272 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 1142 ms 43936 KB
case_02.txt 1128 ms 43972 KB
case_03.txt 1108 ms 44028 KB
case_04.txt 1072 ms 43900 KB
case_05.txt 1074 ms 43728 KB
case_06.txt 1105 ms 43996 KB
case_07.txt 1177 ms 44836 KB
case_08.txt 1374 ms 54304 KB
case_09.txt 1310 ms 50316 KB
case_10.txt 1323 ms 48604 KB
case_11.txt 1314 ms 49208 KB
case_12.txt 1131 ms 44252 KB
case_13.txt 1505 ms 58804 KB
case_14.txt 1977 ms 72288 KB
case_15.txt 1891 ms 73508 KB
case_16.txt 1598 ms 60160 KB
case_17.txt 1986 ms 70032 KB
case_18.txt 1358 ms 50500 KB
case_19.txt 1686 ms 64648 KB
case_20.txt 1793 ms 58836 KB
case_21.txt 1992 ms 76272 KB
case_22.txt 1394 ms 55880 KB
case_23.txt 1942 ms 70516 KB
case_24.txt 1471 ms 56952 KB
case_25.txt 1860 ms 69076 KB
case_26.txt 1494 ms 58608 KB
case_27.txt 1760 ms 60952 KB
case_28.txt 1893 ms 67816 KB
case_29.txt 1322 ms 50848 KB
case_30.txt 1466 ms 59472 KB
sample_01.txt 1087 ms 44000 KB
sample_02.txt 1098 ms 44092 KB
sample_03.txt 1095 ms 44048 KB
sample_04.txt 1138 ms 44588 KB