【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠

作者推荐

【动态规划】【map】【C++算法】1289. 下降路径最小和 II

本文涉及知识点

广度优先搜索拓扑排序逆推

LeetCode913. 猫和老鼠

两位玩家分别扮演猫和老鼠，在一张无向图上进行游戏，两人轮流行动。
图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中，他们必须沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
此外，猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。
示例 1：
输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出：0
示例 2：
输入：graph = [[1,3],[0],[3],[0,2]]
输出：1
提示：
3 <= graph.length <= 50
1 <= graph[i].length < graph.length
0 <= graph[i][j] < graph.length
graph[i][j] != i
graph[i] 互不相同
猫和老鼠在游戏中总是可以移动

广度优先搜索

状态表示： iCat 表示猫位置 iMouse表示老鼠位置 iTurn，表示是否是猫回合。
初始以下情况有确定结果：

老鼠进洞，无论猫在那，谁的回合。
猫抓住老鼠，在同一单格，猫抓到老鼠；老鼠送死。

之后以下情况有确定结果：
猫（老鼠）的回合，猫至少有一个后置状态胜利。猫胜利。
猫（老鼠）的回合，猫至所有的后置状态全部失败。猫失败。
类似与拓扑排序，所有的后置状态都已经确定，或有一个后置状态胜利。将当前状态加到处理队列。
一定不能重复处理，否则计算全部后置状态会错误。
que 待处理队列。
dp各状态的结果
vNextCount 各状态的后置任务数，一个后置任务失败就减1，为0就失败。

代码

核心代码

class Solution {
public:
	int catMouseGame(vector<vector<int>>& graph) {
		m_c = graph.size();
		m_iMaskCount = m_c * m_c * 2;
		queue<int> que;//记录结果确定的状态 后续状态全失败，只会加一次。 后续状态胜利，需要判断重复。
		vector<int> dp(m_iMaskCount),vNextCount(m_iMaskCount);//dp[i]状态为i的结果 vNextCount[i]状态为i有多少种后续状态
		for (int i = 0; i < 2; i++)
		{
			for (int j = 1; j < m_c; j++)
			{
				dp[Mask(j, 0, i)] = 1;//老鼠进洞
				dp[Mask(j, j, i)] = 2;//猫抓住了老鼠
				que.emplace(Mask(j, 0, i));
				que.emplace(Mask(j, j, i));
			}
		}
		for (int iTurn = 0; iTurn < 2; iTurn++)
		{
			for (int iCat = 0; iCat < m_c; iCat++)
			{
				for (int iMouse = 0; iMouse < m_c; iMouse++)
				{
					vNextCount[Mask(iCat, iMouse, iTurn)] = graph[iTurn?iCat:iMouse].size();//如果猫行动，必须扣掉0
				}
			}
		}
		//扣掉猫进洞
		for (int iMouse = 0; iMouse < m_c; iMouse++)
		{
			for (const auto& next : graph[0])
			{
				vNextCount[Mask(next, iMouse,1)]--;
			}
		}
		while (que.size())
		{
			const int iMask = que.front();
			const auto [iCat, iMouse, bCatTrun] = Parse(iMask);			
			que.pop();
			const int iPreTurn = bCatTrun ^ 1;
			bool isWin[] = { 1 == dp[iMask],2 == dp[iMask] };
			for (const auto& prePos : graph[iPreTurn ? iCat : iMouse])
			{
				const int iPreCat = iPreTurn ? prePos : iCat;
				if (0 == iPreCat)
				{
					continue;
				}
				const int iPreMouse = iPreTurn ? iMouse : prePos;
				const int iPreMask = Mask(iPreCat, iPreMouse, iPreTurn);
				if (0 != dp[iPreMask])
				{
					continue;
				}
				const int ifWin = iPreTurn ? 2 : 1;
				if (isWin[iPreTurn] )
				{
					dp[iPreMask] = ifWin;
					que.emplace(iPreMask);
				}
				else
				{
					vNextCount[iPreMask]--;
					if (0 == vNextCount[iPreMask])
					{
						dp[iPreMask] = 3- ifWin;
						que.emplace(iPreMask);
					}
				}
			}
		}		
		return dp[Mask(2,1, false)];
	}
	inline int Mask(int iCat, int iMouse, bool bCatTrun)
	{
		return m_c * 2 * iCat + 2 * iMouse + bCatTrun;
	}
	inline std::tuple<int, int, bool> Parse(int iMask)
	{
		const bool bCatTrun = iMask % 2;
		iMask /= 2;
		return std::make_tuple(iMask / m_c, iMask % m_c, bCatTrun);
	}
	int m_iMaskCount;
	int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<vector<int>> graph;
	{
		Solution sln;
		graph = { {2,5},{3},{0,4,5},{1,4,5},{2,3},{0,2,3} };
		auto res = sln.catMouseGame(graph);
		Assert(res, 0);
	}
	{
		Solution sln;
		graph = { {1,3},{0},{3},{0,2} };
		auto res = sln.catMouseGame(graph);
		Assert(res, 1);
	}
	{
		Solution sln;
		graph = { {2,3},{3,4},{0,4},{0,1},{1,2} };
		auto res = sln.catMouseGame(graph);
		Assert(res, 1);
	}
	

	


}

2023年1月版

class Solution {
public:
int catMouseGame(vector<vector>& graph) {
const int iCatWin = 2;
const int iMouseWin = 1;
const int iMouseTurn = 0;
const int iCatTurn = 1;
m_c = graph.size();
memset(m_dp, 0, sizeof(m_dp));
for (int cat = 0; cat < m_c; cat++)
{
for (int mouse = 0; mouse < m_c; mouse++)
{
m_NextStateNotDo[mouse][cat][iCatTurn] = graph[cat].size();
m_NextStateNotDo[mouse][cat][iMouseTurn] = graph[mouse].size();
}
}
//猫不能进入0洞
for (int mouse = 0; mouse < m_c; mouse++)
{
for (const int& pre0 : graph[0])
{
m_NextStateNotDo[mouse][pre0][iCatTurn] --;
}
}
vector vMaskCanFinish;
for (int i = 1; i < m_c; i++)
{
//相同位置，猫胜
m_dp[i][i][0] = iCatWin;
vMaskCanFinish.push_back(Mask(i, i, 0));
m_dp[i][i][1] = iCatWin;
vMaskCanFinish.push_back(Mask(i, i, 1));
//老鼠进洞
m_dp[0][i][0] = iMouseWin;
vMaskCanFinish.push_back(Mask(0,i, 0));
m_dp[0][i][1] = iMouseWin;
vMaskCanFinish.push_back(Mask(0,i, 1));
}
for (int i = 0; i < vMaskCanFinish.size(); i++)
{
int mouse, cat, iTrun;
ParseMask(mouse, cat, iTrun, vMaskCanFinish[i]);
int iPreTrun = (iTrun + 1) % 2;
if (iCatTurn == iPreTrun)
{
for (auto& pre : graph[cat])
{
if (0 == pre)
{
continue;
}
if (0 != m_dp[mouse][pre][iPreTrun])
{
continue;
}
m_NextStateNotDo[mouse][pre][iPreTrun]–;
if (iCatWin == m_dp[mouse][cat][iTrun])
{
m_dp[mouse][pre][iPreTrun] = iCatWin;
vMaskCanFinish.push_back(Mask(mouse, pre, iPreTrun));
continue;
}
if (0 == m_NextStateNotDo[mouse][pre][iPreTrun])
{
m_dp[mouse][pre][iPreTrun] = iMouseWin;
vMaskCanFinish.push_back(Mask( mouse,pre, iPreTrun));
}
}
}
else
{
for (auto& pre : graph[mouse])
{
if (0 != m_dp[pre][cat][iPreTrun])
{
continue;
}
m_NextStateNotDo[pre][cat][iPreTrun]–;
if (iMouseWin == m_dp[mouse][cat][iTrun])
{
m_dp[pre][cat][iPreTrun] = iMouseWin;
vMaskCanFinish.push_back(Mask(pre, cat, iPreTrun));
continue;
}
if (0 == m_NextStateNotDo[pre][cat][iPreTrun])
{
vMaskCanFinish.push_back(Mask(pre, cat, iPreTrun));
m_dp[pre][cat][iPreTrun] = iCatWin;
}
}
}
}
return m_dp[1][2][0];
}
inline int Mask(const int& mouse, const int& cat, const int& iTrun)
{
return mouse * m_c * 2 + cat * 2 + iTrun;
}
inline void ParseMask(int& mouse, int& cat, int& iTrun, int iMask)
{
mouse = iMask / m_c / 2;
iMask %= (m_c * 2);
cat = iMask / 2;
iTrun = iMask% 2;
}
int m_c;
int m_dp[50][50][2] ;
int m_NextStateNotDo[50][50][2];
};

2023年8月版

class Solution {
public:
int catMouseGame(vector<vector>& graph) {
m_c = graph.size();
std::set set0NeiBo(graph[0].begin(), graph[0].end());
vector vResult(m_cm_c2);
vector vPreMask(m_c * m_c2, -1);//下一种状态，调试用
std::queue que;//依次入队所有具有结果的状态
for (int cat = 0; cat < m_c; cat++)
{
if (0 == cat)
{
continue;
}
{//老鼠移动到同一位置
const int iMask = Mask(1,cat, cat);
que.emplace(iMask);
vResult[iMask] = 1;
}
{//猫移动到同一位置
const int iMask = Mask(0,cat, cat);
que.emplace(iMask);
vResult[iMask] = -1;
}
{//老鼠进洞
const int iMask = Mask(1,0, cat);
que.emplace(iMask);
vResult[iMask] = -1;
}
{//进洞后，猫移动，当前回合：老鼠
const int iMask = Mask(0, 0, cat);
que.emplace(iMask);
vResult[iMask] = 1;
}
}
//当前回合，当前玩家可以移动的可能
vector vCanMoveNum(m_c * m_c * 2),vSucNum(m_cm_c2);
for (int cat = 0; cat < m_c; cat++)
{
if (0 == cat)
{
continue;
}
for (int mouse = 0; mouse < m_c; mouse++)
{
const int iMouseNewMask = Mask(0, mouse, cat);//
vCanMoveNum[iMouseNewMask] = graph[mouse].size();
const int iCatNewMask = Mask(1, mouse, cat);//
vCanMoveNum[iCatNewMask] = graph[cat].size() - set0NeiBo.count(cat);
}
}
while (que.size())
{
const int mask = que.front();
const int curResutl = vResult[mask];
que.pop();
const auto [turn,mouse, cat] = ParseMask(mask);
if (mask== Mask(0,1,2))
{
return (1 == curResutl)? 1 : 2 ;
}
const int preTurn = (1 + turn) % 2;
const int player = (0 == preTurn) ? mouse : cat;
for (const int& move : graph[player])
{
if ((0 == move)&&(1== preTurn))
{//猫不能进洞
continue;
}
const int iPreMask = (0== preTurn) ? Mask(preTurn,move,cat) : Mask(preTurn,mouse,move);
if (- 1 == curResutl)
{
if (0 == vResult[iPreMask])
{
vResult[iPreMask] = 1;
que.emplace(iPreMask);
vPreMask[iPreMask] = mask;
}
continue;
}
vSucNum[iPreMask]–;
if (vCanMoveNum[iPreMask] == -vSucNum[iPreMask])
{
if (0 == vResult[iPreMask])
{
vResult[iPreMask] = -1;
que.emplace(iPreMask);
vPreMask[iPreMask] = mask;
}
}
}
}
return 0;
}
//Turn为0,改老鼠移动；1，猫移动；iMouseNode 移动前老鼠的位置；移动前，猫的位置
int Mask(int iTurn,int iMouseNode,int iCatNode)
{
return iTurnm_c*m_c+iMouseNode * m_c + iCatNode;
}
std::tuple<int,int,int> ParseMask( int iMask)
{
return std::make_tuple<int, int,int>(iMask / m_c/m_c, iMask/m_c%m_c, iMask % m_c);
}
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛