2022-04-08：在一张 无向 图上，节点编号0~N-1。老鼠开始在1节点，猫在2节点

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代码