題意：有一個 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; }

?

轉載于:https://www.cnblogs.com/harden/p/6653834.html

總結

以上是生活随笔為你收集整理的World of Darkraft（codeforces 138D）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。