Submission #144800


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 (sk <- 0 to K) {
    val startToGoal = fromStart(goalY)(goalX)(sk)
    for (i <- 0 until R) {
      for (j <- 0 until C) {
        val b = new Breaks
        b.breakable {
          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
              b.break()
            }
          }
        }
      }
    }
    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 3122 Byte
Status
Exec Time 1921 ms
Memory 77028 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 1062 ms 44472 KB
case_02.txt 1053 ms 44464 KB
case_03.txt 1006 ms 44476 KB
case_04.txt 1014 ms 44344 KB
case_05.txt 1000 ms 44428 KB
case_06.txt 1019 ms 44624 KB
case_07.txt 1079 ms 45316 KB
case_08.txt 1285 ms 55636 KB
case_09.txt 1184 ms 48668 KB
case_10.txt 1214 ms 49324 KB
case_11.txt 1227 ms 49976 KB
case_12.txt 1043 ms 44852 KB
case_13.txt 1457 ms 60368 KB
case_14.txt 1921 ms 71780 KB
case_15.txt 1811 ms 74652 KB
case_16.txt 1466 ms 61900 KB
case_17.txt 1917 ms 71176 KB
case_18.txt 1272 ms 53548 KB
case_19.txt 1612 ms 65452 KB
case_20.txt 1700 ms 63628 KB
case_21.txt 1896 ms 77028 KB
case_22.txt 1327 ms 56684 KB
case_23.txt 1913 ms 70956 KB
case_24.txt 1492 ms 60784 KB
case_25.txt 1763 ms 69016 KB
case_26.txt 1395 ms 57512 KB
case_27.txt 1659 ms 61540 KB
case_28.txt 1780 ms 68912 KB
case_29.txt 1276 ms 53852 KB
case_30.txt 1344 ms 56372 KB
sample_01.txt 1013 ms 44520 KB
sample_02.txt 1005 ms 44604 KB
sample_03.txt 1002 ms 44528 KB
sample_04.txt 1074 ms 45200 KB