2021-08-08：自由之路。电子游戏“辐射4”中，任务“通向自

原创

福大大架构师每日一题

修改于 2021-08-09 03:26:10

3600

2021-08-08：自由之路。电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。旋转 ring 拼出 key 字符 keyi 的阶段中：您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 keyi 。如果字符 keyi 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

福大大答案2021-08-08：

递归。具体见代码。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {
    ring := "godding"
    key := "gd"
    ret := findRotateSteps(ring, key)
    fmt.Println(ret)
}

func findRotateSteps(r string, k string) int {
    N := len(r)
    map0 := make(map[byte][]int)
    for i := 0; i < N; i++ {
        if _, ok := map0[r[i]]; !ok {
            map0[r[i]] = make([]int, 0)
        }
        map0[r[i]] = append(map0[r[i]], i)
    }
    M := len(k)
    dp := make([][]int, N)
    for i := 0; i < N; i++ {
        dp[i] = make([]int, M+1)
    }
    for i := 0; i < N; i++ {
        for j := 0; j <= M; j++ {
            dp[i][j] = -1
        }
    }
    return process(0, 0, k, map0, N, dp)
}

// 电话里：指针指着的上一个按键preButton
// 目标里：此时要搞定哪个字符？keyIndex
// map : key 一种字符 value: 哪些位置拥有这个字符
// N: 电话大小
// f(0, 0, aim, map, N)
func process(preButton int, index int, str string, map0 map[byte][]int, N int, dp [][]int) int {
    if dp[preButton][index] != -1 {
        return dp[preButton][index]
    }
    ans := math.MaxInt64
    if index == len(str) {
        ans = 0
    } else {
        // 还有字符需要搞定呢！
        cur := str[index]
        nextPositions := map0[cur]
        for _, next := range nextPositions {
            cost := dial(preButton, next, N) + 1 + process(next, index+1, str, map0, N, dp)
            ans = getMin(ans, cost)
        }
    }
    dp[preButton][index] = ans
    return ans
}

func dial(i1 int, i2 int, size int) int {
    return getMin(Abs(i1-i2), getMin(i1, i2)+size-getMax(i1, i2))
}

func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func Abs(a int) int {
    if a < 0 {
        return -a
    } else {
        return a
    }
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}