Submission #144762


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
          }
        }
      }
    }
    val gk = K - sk
    answer = answer min (fromStart(compY)(compX)(sk) + fromGoal(compY)(compX)(gk))
  }



  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 3017 Byte
Status
Exec Time 1997 ms
Memory 73660 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 1223 ms 44496 KB
case_02.txt 1146 ms 44524 KB
case_03.txt 1104 ms 44408 KB
case_04.txt 1069 ms 44408 KB
case_05.txt 1168 ms 44436 KB
case_06.txt 1152 ms 44544 KB
case_07.txt 1235 ms 45312 KB
case_08.txt 1423 ms 54960 KB
case_09.txt 1286 ms 48748 KB
case_10.txt 1324 ms 49456 KB
case_11.txt 1308 ms 49860 KB
case_12.txt 1121 ms 44680 KB
case_13.txt 1466 ms 55476 KB
case_14.txt 1981 ms 68876 KB
case_15.txt 1978 ms 73660 KB
case_16.txt 1549 ms 61200 KB
case_17.txt 1997 ms 67400 KB
case_18.txt 1383 ms 50788 KB
case_19.txt 1667 ms 61824 KB
case_20.txt 1830 ms 64364 KB
case_21.txt 1971 ms 73552 KB
case_22.txt 1403 ms 56220 KB
case_23.txt 1969 ms 67332 KB
case_24.txt 1521 ms 60324 KB
case_25.txt 1786 ms 64896 KB
case_26.txt 1479 ms 57800 KB
case_27.txt 1759 ms 61100 KB
case_28.txt 1901 ms 69104 KB
case_29.txt 1330 ms 51412 KB
case_30.txt 1422 ms 56440 KB
sample_01.txt 1105 ms 44552 KB
sample_02.txt 1076 ms 44536 KB
sample_03.txt 1072 ms 44420 KB
sample_04.txt 1215 ms 45060 KB