A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.html
The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.node
Mouse starts at node 1 and goes first, Cat starts at node 2 and goes second, and there is a Hole at node 0.git
During each player's turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].github
Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)数组
Then, the game can end in 3 ways:函数
Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.动画
Example 1:this
Input: [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0 Explanation: 4---3---1 | | 2---5 \ / 0
Note:code
3 <= graph.length <= 50graph[1] is non-empty.graph[2] contains a non-zero element.
这道题是猫抓老鼠的问题，Tom and Jerry 都看过吧，小时候看着笑到肚子疼的一部动画片，真是经典中的经典。这道题在无向图上模仿了猫抓老鼠的这一个过程，老鼠位于结点1，猫位于结点2，老鼠的目标是逃回老鼠洞结点0，猫的目标是在老鼠进洞以前抓住它。这里假设猫和老鼠都不是沙雕，都会选择最优的策略。若老鼠能成功逃回洞里，则返回1；若猫能成功抓到老鼠，则返回2；若谁也不能达到目标，则表示平局，返回0。其实这道题的本质仍是一个无向图的遍历问题，只不过如今有两个物体在遍历，比通常的图遍历要复杂一些。假设图中有n个结点，不管是猫仍是老鼠，当各自走完了n个结点时尚未分出胜负，则表示平局，若一人走一步，则最多有 2n 步。这样的话每个状态其实是由三个因素组成的：当前步数，老鼠所在结点，和猫所在结点。这里能够用动态规划 Dynamic Programming 来解，使用一个三维的 dp 数组，其中 dp[t][x][y] 表示当前步数为t，老鼠在结点x，猫在结点y时最终会返回的值，均初始化为 -1。要求的实际上是起始状态 dp[0][1][2] 的返回值，但无法一会儿求出，这个起始状态其实是要经过其余状态转移过来，就好比说是求二叉树最大深度的递归函数，虽然对根结点调用递归函数的返回值就是最大深度，但在函数遇到叶结点以前都没法得知深度。先来看一些终止状态，首先当老鼠到达洞口的时候，此时老鼠赢，返回值是1，即全部 dp[?][0][?] 状态的返回值都是1。其次，当猫和老鼠处于同一个位置时，表示猫抓到老鼠了，此时猫赢，返回值是2，即全部 dp[?][y][y] 状态的返回值都是2。最后，当走完了 2n 步尚未分出胜负的话，则是平局，直接返回0便可。htm
理清了上面的思路，其实代码就不难写了，这里使用递归的写法，在递归函中，首先判断步数是否到了 2n，是的话直接返回0；不然判断x和y是否相等，是的话当前状态赋值为2并返回；不然再判断x是否等于0，是的话当前状态赋值为1并返回。若当前状态的 dp 值不是 -1，则表示以前已经更新过了，不须要重复计算了，直接返回便可。不然就要来计算当前的 dp 值，先肯定当前该谁走，只要判断t的奇偶便可，由于最开始步数0的时候是老鼠先走。若此时该老鼠走了，它能走的相邻结点能够在 graph 中找到，对于每个能够到达的相邻结点，都调用递归函数，此时步数是 t+1，老鼠位置为相邻结点，猫的位置不变。若返回值是1，表示老鼠赢，则将当前状态赋值为1并返回；若返回状态是2，此时不能立马返回猫赢，由于老鼠能够不走这个结点；若返回值是0，表示老鼠走这个结点是有平局的机会，但老鼠仍是要争取赢的机会，因此此时用一个 bool 变量标记下猫确定赢不了，但此时也不能直接返回，由于 Jerry 一直要追寻赢的机会。直到遍历完了全部可能性，老鼠最终仍是没有赢，则看下以前那个 bool 型变量 catWin，若为 true，则标记当前状态为2并返回，反之，则标记当前状态为0并返回。若此时该猫走了，基本跟老鼠的策略相同，它能走的相邻结点也能够在 graph 中找到，对于每个能够到达的相邻结点，首先要判断是否为结点0（老鼠洞），由于猫是不能进洞的，因此要直接跳过这个结点。不然就调用递归函数，此时步数是 t+1，老鼠位置不变，猫的位置为相邻结点。若返回值是2，表示猫赢，则将当前状态赋值为2并返回；若返回状态是1，此时不能立马返回老鼠赢，由于猫能够不走这个结点；若返回值是0，表示猫走这个结点是有平局的机会，但猫仍是要争取赢的机会，因此此时用一个 bool 变量标记下老鼠确定赢不了，但此时也不能直接返回，由于 Tom 也一直要追寻赢的机会。直到遍历完了全部可能性，猫最终仍是没有赢，则看下以前那个 bool 型变量 mouseWin，若为 true，则标记当前状态为1并返回，反之，则标记当前状态为0并返回，参见代码以下：
class Solution {
public:
int catMouseGame(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<vector<int>>> dp(2 * n, vector<vector<int>>(n, vector<int>(n, -1)));
return helper(graph, 0, 1, 2, dp);
}
int helper(vector<vector<int>>& graph, int t, int x, int y, vector<vector<vector<int>>>& dp) {
if (t == graph.size() * 2) return 0;
if (x == y) return dp[t][x][y] = 2;
if (x == 0) return dp[t][x][y] = 1;
if (dp[t][x][y] != -1) return dp[t][x][y];
bool mouseTurn = (t % 2 == 0);
if (mouseTurn) {
bool catWin = true;
for (int i = 0; i < graph[x].size(); ++i) {
int next = helper(graph, t + 1, graph[x][i], y, dp);
if (next == 1) return dp[t][x][y] = 1;
else if (next != 2) catWin = false;
}
if (catWin) return dp[t][x][y] = 2;
else return dp[t][x][y] = 0;
} else {
bool mouseWin = true;
for (int i = 0; i < graph[y].size(); ++i) {
if (graph[y][i] == 0) continue;
int next = helper(graph, t + 1, x, graph[y][i], dp);
if (next == 2) return dp[t][x][y] = 2;
else if (next != 1) mouseWin = false;
}
if (mouseWin) return dp[t][x][y] = 1;
else return dp[t][x][y] = 0;
}
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/913
参考资料：