网站建设岗位的简介,百度收录最高发帖网站,wordpress显示加载耗时,东莞公司建站模板作者推荐
【动态规划】【map】【C算法】1289. 下降路径最小和 II
本文涉及知识点
广度优先搜索 拓扑排序 逆推
LeetCode913. 猫和老鼠
两位玩家分别扮演猫和老鼠#xff0c;在一张 无向 图上进行游戏#xff0c;两人轮流行动。 图的形式是#xff1a;graph[a] 是一个列…作者推荐
【动态规划】【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(vectorvectorint graph) {m_c graph.size();m_iMaskCount m_c * m_c * 2;queueint que;//记录结果确定的状态 后续状态全失败只会加一次。 后续状态胜利需要判断重复。vectorint 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::tupleint, 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;
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{ vectorvectorint 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(vectorvector 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(vectorvector 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_ciMouseNode * m_c iCatNode; } std::tupleint,int,int ParseMask( int iMask) { return std::make_tupleint, 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
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 **C
17** 如无特殊说明本算法用**C**实现。
