[LeetCode]Cat and Mouse

游戏类的题，每一个玩家都是做optimal move，结果最后是什么。首先我们想到的应该就是minimax tree的思路，我们可以用mouse代表老鼠的位置，cat代表猫的位置，turn代表当前的player(1代表老鼠，2代表猫)，那么可以用(mouse, cat, turn)代表当前的状态，假设输入图总共有n个节点:

• (1, 2, 1)是起始状态
• (0, i, k)是老鼠获胜的状态, 其中1 <= i < n, 1 <= k <= 2
• (i, i, k)是猫获胜的状态，其中1 <= i < n, 1 <= k <= 2

我们只需要从起始开始状态递归即可，每个节点(i, j, k)当前的player都取最优的move:

• 如果某个相邻节点的结果是对手无法获胜，当前player取的肯定是这个move，所以当前状态肯定获胜
• 否则，如果有draw的节点，会取这个move，所以当前节点对应的状态下的结果就是draw
• 如果以上两点都不成立，说明当前节点没有任何一个move可以导致获胜或者平局的结果，所以一定会输

用这种思路我们可以写出DFS的minimax做法，我们需要一个hashset来检测环的存在。但是这种方法在处理较大的数据时会TLE。代码如下：

	class Solution {
	public:
	int catMouseGame(vector<vector<int>>& graph) {
	unordered_set<string> states;
	int res = canWin(graph, 1, 2, 1, states);
	return res == 2 ? 1 : (res == 1 ? 0 : 2);
	}
	private:
	//1 == mouse
	//2 == cat
	//return 0 lose, 1 draw, 2 win
	int canWin(const vector<vector<int>>& graph, int mouse, int cat, int player, unordered_set<string>& states)
	{
	if (mouse == cat)return player == 1 ? 0 : 2;
	if (mouse == 0)return player == 1 ? 2 : 0;
	string state = to_string(mouse) + "," + to_string(cat) + "," + to_string(player);
	if (states.find(state) != states.end())return 1;
	states.insert(state);
	int canHeWin = 2;
	for (auto& next : graph[player == 1 ? mouse : cat])
	{
	if (next == 0 && player == 2)continue;
	int heWins = canWin(graph, player == 1 ? next : mouse, player == 1 ? cat : next, player == 1 ? 2 : 1, states);
	if (heWins == 0)
	{
	states.erase(state);
	return 2;
	}
	if (heWins == 1)canHeWin = 1;
	}
	states.erase(state);
	return canHeWin == 1 ? 1 : 0;
	}
	};

view raw Cat and Mouse_dfs_minmax.cpp hosted with ❤ by GitHub

我们自然会思考可能的优化，比如我们用memorization的思路，对于每一个状态(mouse, cat, turn)我们存下他们对应的结果，这样在之后在到达这个节点的时候直接return即可。代码如下：

	class Solution {
	public:
	int catMouseGame(vector<vector<int>>& graph) {
	unordered_set<string> states;
	//0 draw, 1 mouse wins, 2 cat wins
	unordered_map<string, int> memo;
	int res = canWin(graph, 1, 2, 1, states, memo);
	return res == 2 ? 1 : (res == 1 ? 0 : 2);
	}
	private:
	//1 == mouse
	//2 == cat
	//return 0 lose, 1 draw, 2 win
	int canWin(const vector<vector<int>>& graph, int mouse, int cat, int player, unordered_set<string>& states, unordered_map<string, int>& memo)
	{
	if (mouse == cat)return player == 1 ? 0 : 2;
	if (mouse == 0)return player == 1 ? 2 : 0;
	string state = to_string(mouse) + "," + to_string(cat) + "," + to_string(player);
	if (memo.find(state) != memo.end())
	{
	if (memo[state] == 0)return 1;
	else return memo[state] == player ? 2 : 0;
	}
	if (states.find(state) != states.end())return 1;
	states.insert(state);
	int canHeWin = 2;
	for (auto& next : graph[player == 1 ? mouse : cat])
	{
	if (next == 0 && player == 2)continue;
	int heWins = canWin(graph, player == 1 ? next : mouse, player == 1 ? cat : next, player == 1 ? 2 : 1, states, memo);
	if (heWins == 0)
	{
	memo[state] = player;
	states.erase(state);
	return 2;
	}
	if (heWins == 1)canHeWin = 1;
	}
	states.erase(state);
	int winner = canHeWin ? 3 - player : 0;
	memo[state] = winner;
	return canHeWin == 1 ? 1 : 0;
	}
	};

view raw Cat and Mouse_dfs_minmax_memo.cpp hosted with ❤ by GitHub

这种思路乍看之下没有错，并且可以过绝大部分test case，但是对于一些特殊的test case他会fail，比如对于如下的状态图:

图一

如图一所示，其中每一个节点代表一个状态(mouse, cat, turn)。假设我们从1开始dfs，假设我们先取了1->4->3->2->1这条路径，那么我们就会把2, 3, 4在dfs的时候都在memo里mark成draw，但是事实上他们都应该mark成winning。

换句话说，dfs + memorization在处理cycle的时候会把某些节点错误地mark成draw，然而这些点真实的状态可能是在之后dfs找到的其他状态。

为了解决这个问题，我们可以用BFS从所有确定的状态开始，把每个能够确定状态的节点标记:

• 对于当前节点，假设赢家为winner，我们把相邻的节点turn为winner的节点的赢家也标记成winner
• 对于相邻节点turn不为winner的节点，我们将其degree(邻接节点的数量)减一。当其减为0的时候，代表当前节点任何一个move都是输，我们将赢家标记成对手

整体的思路和上面讲的dfs minimax的思路是类似的。这样我们从一定确定状态的节点开始BFS并且mark所有节点的话，就不会有之前提到的问题。时间复杂度O(N^3)，我们总共有O(N^2)个状态，每个节点最多对对应N个邻接节点。代码如下：

	struct State
	{
	int mouse, cat, turn, winner;
	State(int m, int c, int t, int w)
	{
	mouse = m;
	cat = c;
	turn = t;
	winner = w;
	}
	};
	class Solution {
	public:
	int catMouseGame(vector<vector<int>>& graph) {
	int n = graph.size();
	//1 mouse, 2 cat
	vector<vector<vector<int>>> color(n, vector<vector<int>>(n, vector<int>(3, 0)));
	vector<vector<vector<int>>> degree(n, vector<vector<int>>(n, vector<int>(3, 0)));
	//init degree
	for(int i = 0; i < n; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	degree[i][j][1] = graph[i].size();
	degree[i][j][2] = graph[j].size();
	//cat cannot reach node 0
	for(int node : graph[j])
	{
	if(!node)
	{
	--degree[i][j][2];
	break;
	}
	}
	}
	}
	//bfs to mark wining state for each node, 0 draw, 1 mouse wins, 2 cat wins
	queue<State> q;
	//init queue
	for(int i = 0; i < n; ++i)
	{
	for(int k = 1; k <= 2; ++k)
	{
	if(i)
	{
	//mouse wins
	color[0][i][k] = 1;
	q.emplace(0, i, k, 1);
	//cat wins
	color[i][i][k] = 2;
	q.emplace(i, i, k, 2);
	}
	}
	}
	//mark wining state for each node
	while(q.size())
	{
	auto state = q.front();
	int m = state.mouse, c = state.cat, t = state.turn, w = state.winner;
	q.pop();
	auto neighbors = adjs(graph, m, c, t);
	for(const auto& curr : neighbors)
	{
	int mouse = curr[0], cat = curr[1], turn = curr[2];
	//if curr is not colored
	if(color[mouse][cat][turn] != 0)continue;
	//wining state for current player
	if(w == turn)
	{
	color[mouse][cat][turn] = w;
	q.emplace(mouse, cat, turn, w);
	}
	//if not, decrease degree count, if it reaches zero
	//there is no way for current player to win
	else
	{
	--degree[mouse][cat][turn];
	if(!degree[mouse][cat][turn])
	{
	color[mouse][cat][turn] = 3 - turn;
	q.emplace(mouse, cat, turn, 3 - turn);
	}
	}
	}
	}
	return color[1][2][1];
	}
	private:
	//nodes can arrive (mouse, cat, turn) by playing their turn
	vector<vector<int>> adjs(const vector<vector<int>>& graph, int mouse, int cat, int turn)
	{
	vector<vector<int>> res;
	if(turn == 2)
	{
	for(const int next : graph[mouse])
	res.push_back({next, cat, 3 - turn});
	}
	else
	{
	for(const int next : graph[cat])
	if(next)res.push_back({mouse, next, 3 - turn});
	}
	return res;
	}
	};

view raw Cat and Mouse_bfs_minmax.cpp hosted with ❤ by GitHub