首页 > 代码库 > World of Darkraft(codeforces 138D)
World of Darkraft(codeforces 138D)
题意:有一个 n × m 的棋盘,每个点上标记了 L; R; X 中的一个
每次能选择一个没有被攻击过的点 (i; j),从这个点开始发射线,射线形状为:
1. 若字符是 L,向左下角和右上角发,遇到被攻击过的点就停下来
2. 若字符是 R,向左上角和右下角发,遇到被攻击过的点就停下来
3. 若字符是 X,向左小左上右下右上发,遇到被攻击过的点停下来
问先手是否必胜, n; m ≤ 20
/* 首先可以根据激光的性质,把图进行奇偶划分,然后就变成了两个子问题。 当出现一道激光时,这个游戏就变成了2个或4个完全等价的游戏,可以根据这个特点设计SG函数。 */ #include<cstdio> #include<cstring> #include<iostream> #define N 50 using namespace std; int n,m,dp[N][N][N][N][2]; char map[N][N]; int dfs(int min_x,int max_x,int min_y,int max_y,int op){ int ret=dp[min_x][max_x][min_y][max_y][op]; if(ret!=-1) return ret; char s[N]={0}; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if((i+j&1)==op){ int x=i+j,y=i-j+m; if(x>=min_x&&x<max_x&&y>=min_y&&y<max_y){ int g=0; if(map[i][j]==‘L‘) g=dfs(min_x,x,min_y,max_y,op)^dfs(x+1,max_x,min_y,max_y,op); if(map[i][j]==‘R‘) g=dfs(min_x,max_x,min_y,y,op)^dfs(min_x,max_x,y+1,max_y,op); if(map[i][j]==‘X‘) g=dfs(min_x,x,min_y,y,op)^dfs(min_x,x,y+1,max_y,op) ^dfs(x+1,max_x,min_y,y,op)^dfs(x+1,max_x,y+1,max_y,op); s[g]=1; } } while(s[++ret]); dp[min_x][max_x][min_y][max_y][op]=ret; return ret; } int main(){ memset(dp,-1,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",map[i]); int t=dfs(0,n+m,0,n+m,0)^dfs(0,n+m,0,n+m,1); if(t) printf("WIN"); else printf("LOSE"); return 0; }
World of Darkraft(codeforces 138D)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。