結果

問題 No.34 砂漠の行商人
ユーザー バカらっくバカらっく
提出日時 2019-09-07 18:54:35
言語 Kotlin
(1.9.23)
結果
TLE  
実行時間 -
コード長 1,827 bytes
コンパイル時間 17,991 ms
コンパイル使用メモリ 453,008 KB
実行使用メモリ 135,164 KB
最終ジャッジ日時 2024-06-27 01:08:09
合計ジャッジ時間 32,178 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 327 ms
60,388 KB
testcase_01 AC 326 ms
95,104 KB
testcase_02 AC 388 ms
59,520 KB
testcase_03 AC 340 ms
56,940 KB
testcase_04 AC 1,023 ms
97,832 KB
testcase_05 AC 960 ms
97,200 KB
testcase_06 AC 484 ms
68,996 KB
testcase_07 AC 1,355 ms
101,400 KB
testcase_08 AC 1,714 ms
103,760 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:3:10: warning: parameter 'arr' is never used
fun main(arr:Array<String>) {
         ^
Main.kt:55:40: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Int
        ans = step[gy][gx].values.min()!!
                                       ^

ソースコード

diff # 

import java.util.*

fun main(arr:Array<String>) {
    val inpt = readLine()!!.trim().split(" ").map { it.toInt() }
    val (n, v) = inpt.take(2)
    val (sx, sy, gx, gy) = inpt.drop(2).map { it - 1 }

    val map = (1..n).map { readLine()!!.split(" ").map { it.toInt() }.toTypedArray() }.toTypedArray()
    val step = map.map { it.map { mutableMapOf<Int, Int>() }.toTypedArray() }.toTypedArray()

    val queue = ArrayDeque<Task>(n*n)
    var min = n * n + 1
    queue.add(Task(sx, sy, v, 0))
    while (queue.isNotEmpty()) {
        val t = queue.pop()
        if(t.vital <= 0) {
            continue
        }
        if(t.step > min) {
            continue
        }
        var skip = false
        step[t.y][t.x][t.vital]?.also {
            if(it <= t.step) {
                skip = true
            }
        }
        if(step[t.y][t.x].filter { it.key >= t.vital && it.value <= t.step }.isNotEmpty()) {
            skip = true
        }
        if(skip) {
            continue
        } else {
            step[t.y][t.x][t.vital] = t.step
        }
        if(t.x == gx && t.y == gy) {
            min = Math.min(min, t.step)
            continue
        }
        if(t.y > 0) {
            queue.add(Task(t.x, t.y - 1, t.vital - map[t.y - 1][t.x], t.step + 1))
        }
        if(t.y < n - 1) {
            queue.add(Task(t.x, t.y + 1, t.vital - map[t.y + 1][t.x], t.step + 1))
        }
        if(t.x > 0) {
            queue.add(Task(t.x - 1, t.y, t.vital - map[t.y][t.x - 1], t.step + 1))
        }
        if(t.x < n - 1) {
            queue.add(Task(t.x + 1, t.y, t.vital - map[t.y][t.x + 1], t.step + 1))
        }
    }
    var ans = -1
    if(step[gy][gx].isNotEmpty()) {
        ans = step[gy][gx].values.min()!!
    }
    println(ans)
}

data class Task(val x:Int, val y:Int, val vital:Int, val step:Int)
0