[白俊]1697号:-Kotlin


質問する
https://www.acmicpc.net/problem/1697
に答える
  • 現在の位置はxであり、xは常に3つの子を持っている.
  • (範囲内の場合)
  • 子の範囲を確認し、訪問したことのない場所であれば訪問します.
  • nが60000、kが100000の場合、n 2の値から徐々に下がる過程はもっと速いと思いますが、60000万から50000、さらに100000まで、効率はもっと高くなります!だからn 2を作るときは100000以下がいい!
  • import java.util.*
    
    fun traverse(queue: Queue<Pair<Int, Int>>, visited: Array<Boolean>, nDest: Int, count: Int) {
        if (nDest in 0 until 100001 && !visited[nDest]) {
            queue.add(Pair(nDest, count + 1))
            visited[nDest] = true
        }
    }
    
    fun main() {
        val br = System.`in`.bufferedReader()
        val bw = System.out.bufferedWriter()
        val (n, k) = br.readLine().split(" ").map { it.toInt() }
        val queue: Queue<Pair<Int, Int>> = LinkedList()
        val visited = Array(100001) { false }
        queue.add(Pair(n, 0))
        visited[n] = false
        var result = 0
        while (queue.isNotEmpty()) {
            val (dest, count) = queue.poll()
            if (dest == k) {
                result = count
                break
            }
            traverse(queue, visited, dest + 1, count)
            traverse(queue, visited, dest - 1, count)
            traverse(queue, visited, dest * 2, count)
        }
        bw.write("$result")
        br.close()
        bw.close()
    }

    もっと良い方法があればメッセージを残してください!!