首页 > 代码库 > 记忆化搜索（游戏NOIP17提高模拟训练11）
记忆化搜索（游戏NOIP17提高模拟训练11）
Alice和Bob在玩一个游戏，游戏是在一个N*N的矩阵上进行的，每个格子上都有
一个正整数。当轮到Alice/Bob时，他/她可以选择最后一列或最后一行，并将其删除，但
必须保证选择的这一行或这一列所有数的和为偶数。如果他/她不能删除最后一行或最后一
列，那么他/她就输了。两人都用最优策略来玩游戏，Alice先手，问Alice是否可以必胜？
输入格式：
第一行：T，表示数据组数
对于每组数据的第一行：N
接下来N行，每行N个数，描述这个矩阵
输出格式：
如果Alice必胜输出W，否则输出L
样例输入：
222 46 835 4 21 5 97 3 8
样例输出：
LW
数据范围：
100%数据满足
1<=N<=1000
保证每一行或每一列的和不会超过2*10^9
1<=T<=5
30%数据满足
1<=N<=5
50%数据满足
1<=N<=100
70%数据满足
1<=N<=500
时间限制：
2S
空间限制：
256M
思路就是记忆化搜索，每一次标记一下是谁下这个点。可以预处理一下数据，加快运行的速度。
#include<bits/stdc++.h>using namespace std; int Map[2000][2000],hang[2000][2000],lie[2000][2000];bool book [2000][2000][2];bool dp[2000][2000][2];int n; bool dfs(int i,int j,bool point){ if(i==0||j==0) return 0; if(book[i][j][point]) return dp[i][j][point]; if(hang[i][j]%2==0) dp[i][j][point]=!dfs(i-1,j,point^1); if(lie[i][j]%2==0) { if(!dfs(i,j-1,point^1)||dp[i][j][point]) dp[i][j][point]=1 ; else dp[i][j][point]=0; } book[i][j][point]=1; return dp[i][j][point];} int main(){ int t; cin>>t; while(t--) { memset(Map,0,sizeof(Map));memset(lie,0,sizeof(lie));memset(dp,0,sizeof(dp));memset(hang,0,sizeof(hang)); memset(book,0,sizeof(book)); cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>Map[i][j]; hang[i][j]=hang[i][j-1]+Map[i][j]; } for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) lie[i][j]=lie[i-1][j]+Map[i][j]; if(dfs(n,n,0))cout<<"W\n"; else cout<<"L\n"; } return 0;}
记忆化搜索（游戏NOIP17提高模拟训练11）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。