首页 > 代码库 > Codeforces 138D World of Darkraft（Multi-Nim）
Codeforces 138D World of Darkraft（Multi-Nim）
【题目链接】 http://codeforces.com/problemset/problem/138/D
【题目大意】
H*W的棋盘中每个点都是L、R、X三者之一，两人轮流选一个点，
若为L则向左下和右上发射激光，R向右下和左上发射，
X则相当于LR的组合——同时向四个方向发射。激光所至的点会被摧毁，
只有已摧毁的点或棋盘边界才会挡住激光。
若在某回合开始时所有点都被摧毁，则该人失败。问先手是否有必胜策略？
【题解】
我们根据激光将棋盘切成不同的不同的部分，
将几个子游戏的sg异或起来作为整个游戏的sg值，
以为激光是斜着切的所以我们把棋盘转一转方便处理，
此外棋盘的奇偶格子是互不干扰的因此我们分开计算其sg值并异或起来判断答案
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;char mp[30][30];int sg[50][50][50][50][2],n,m;int SG(int x1,int x2,int y1,int y2,int k){ int &ret=sg[x1][x2][y1][y2][k]; if(ret!=-1)return ret; char s[60]={0}; for(int y=0;y<n;y++){ for(int x=0;x<m;x++){ if(((x+y)&1)==k){ int _x=y+x,_y=y-x+m; if(x1<=_x&&_x<x2&&y1<=_y&&_y<y2){ char c=mp[y][x]; int g=0; if(c==‘L‘)g=SG(x1,_x,y1,y2,k)^SG(_x+1,x2,y1,y2,k); if(c==‘R‘)g=SG(x1,x2,y1,_y,k)^SG(x1,x2,_y+1,y2,k); if(c==‘X‘){ g=SG(x1,_x,y1,_y,k); g^=SG(x1,_x,_y+1,y2,k); g^=SG(_x+1,x2,y1,_y,k); g^=SG(_x+1,x2,_y+1,y2,k); }s[g]=1; } } } }while(s[++ret]); return ret;}int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;i++)scanf("%s",mp[i]); memset(sg,-1,sizeof(sg)); puts(SG(0,n+m,0,n+m,0)^SG(0,n+m,0,n+m,1)?"WIN":"LOSE"); }return 0;}Codeforces 138D World of Darkraft（Multi-Nim）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。