作者推荐
【动态规划】【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;
};
