【力扣·每日一题】913. 猫和老鼠（C++ 记忆化搜索 博弈）

【力扣·每日一题】913. 猫和老鼠（C++ 记忆化搜索 博弈）

​​linkk​​

题意：

思路：

采用记忆化搜索，dp[t][x][y]表示走了t步后老鼠在x猫在y时的状态。 初始将dp数组都设为-1，表示未被经过。 dfs搜索，传的参数未当前的步数t，老鼠的位置x，猫的位置y。然后进行判断：

如果当前的步数>=2n 返回0平局如果x=y 则猫赢 返回2如果x=0 老鼠赢 返回1对老鼠而言，遍历相邻的节点时 如果返回值为1 则老鼠肯定赢；如果返回值为2，则老鼠可以不走这一步；如果返回值为0，则可能是平局，但猫一定赢不了，所以标记flag=false；最后判断flag的值，如果flag为true的话，说明是老鼠输了；否则，为平局。猫的过程也同理。

注意：猫不能走0

代码：

class Solution {public: int catMouseGame(vector>& graph) { int n=graph.size(); vector>>dp(2*n,vector>(n,vector(n,-1))); return dfs(graph,0,1,2,dp); } int dfs(vector>&graph,int t,int x,int y,vector>>&dp){ if(t==graph.size()*2) return 0; if(x==y){ dp[t][x][y]=2;return 2; } if(x==0){ dp[t][x][y]=1;return 1; } if(dp[t][x][y]!=-1) return dp[t][x][y]; if(t%2==0){//老鼠走 bool flag=true; for(auto tt:graph[x]){ int now=dfs(graph,t+1,tt,y,dp); if(now==1){ dp[t][x][y]=1;return 1; } else if(now==0){ flag=false; } } if(flag){ dp[t][x][y]=2;return 2; } else{ dp[t][x][y]=0;return 0; } } else{//猫走 bool flag=true; for(auto tt:graph[y]){ if(tt==0) continue; int now=dfs(graph,t+1,x,tt,dp); if(now==2){ dp[t][x][y]=2;return 2; } else if(now==0){ flag=false; } } if(flag){ dp[t][x][y]=1;return 1; } else{ dp[t][x][y]=0;return 0; } } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。