2022-04-08：在一张 无向 图上，节点编号0~N-1。老鼠开始在1节点，猫在2节点，0号节点是洞，老鼠想进洞，
老鼠第先出发，猫后出发，轮流行动。
在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动，
此外猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏，返回谁获胜。
福大大答案2022-04-08：
递归。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
graph := [][]int{{1, 3}, {0}, {3}, {0, 2}}
ret := catMouseGame2(graph)
fmt.Println(ret)
}
func catMouseGame2(graph [][]int) int {
n := len(graph)
// 这里！
// int limit = (n << 1) + 2; 还会出错，但是概率很小，需要多跑几次
// int limit = (n << 1) + 3; 就没错了，或者说，概率小到很难重现
// 为啥？我屌你为啥！
// n * 2 + 2
limit := (n << 1) + 3
dp := make([][][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([][]int, n)
for j := 0; j < n; j++ {
dp[i][j] = make([]int, limit)
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
for k := 0; k < limit; k++ {
dp[i][j][k] = -1
}
}
}
return process(graph, limit, 2, 1, 1, dp)
}
// dp[][][] 傻缓存！
// dp[cat][mouse][turn] == -1 这个状态之前没算过！
// dp[cat][mouse][turn] == 0 这个状态之前算过！平局！
// dp[cat][mouse][turn] == 1 这个状态之前算过！老鼠赢！
// dp[cat][mouse][turn] == 2 这个状态之前算过！猫赢！
// 固定参数！轮数不要超过limit！如果超过，就算平局！
func process(graph [][]int, limit int, cat, mouse, turn int, dp [][][]int) int {
if turn == limit {
return 0
}
if dp[cat][mouse][turn] != -1 {
return dp[cat][mouse][turn]
}
ans := 0
if cat == mouse {
ans = 2
} else if mouse == 0 {
ans = 1
} else {
if (turn & 1) == 1 { // 老鼠回合
ans = 2
for _, next := range graph[mouse] {
p := process(graph, limit, cat, next, turn+1, dp)
ans = twoSelectOne(p == 1, 1, twoSelectOne(p == 0, 0, ans))
if ans == 1 {
break
}
}
} else { // 猫回合
ans = 1
for _, next := range graph[cat] {
if next != 0 {
p := process(graph, limit, next, mouse, turn+1, dp)
ans = twoSelectOne(p == 2, 2, twoSelectOne(p == 0, 0, ans))
if ans == 2 {
break
}
}
}
}
}
dp[cat][mouse][turn] = ans
return ans
}
func twoSelectOne(c bool, a, b int) int {
if c {
return a
} else {
return b
}
}
执行结果如下：
左神java代码
