辐射4自由之路（任务“通向自由”）

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

执行结果如下：

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class03/Code07_FreedomTrail.java)