题意：n*m个格子，有若干炸弹。对于在第一行或者第一列的炸弹，爆炸后会到那一行或者那一列的更前面（总的来说就是更靠近左上角）的位置。对于其他位置的炸弹，爆炸后会生成两个炸弹，分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。
大概明白了一点。整个游戏可以分为若干个炸弹的游戏的和，而实际上一个不在边界行或者列的炸弹，依然可以继续分，分成两个炸弹的和。而位于(i.j)的炸弹，分成两个炸弹的和，有(i-1)*(j-1)种方案（这个不重要2333）
处于边界行或者列的点的sg值我们是可以知道的。。因为规则单一。。和移动等价。。
然后根据边界来进一步处理一般的情况。。
有点类似dp的思想。。。？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
/* *********************************************** Author :111qqz Created Time :2016年07月23日 星期六 04时52分16秒 File Name :code/hdu/2873.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=55; int n,m; int sg[N][N]; bool vis[N*N]; char maze[N][N]; int px[N],py[N]; void sg_init() { ms(sg,0); for ( int i = 0 ; i < N ; i++) //在边界的只能往一个方向生成炸弹，和移动了炸弹等价。 sg[i][0]=sg[0][i]=i; //还是0based好一点。。。这样（1,1）点的sg值自然就是0了。。。 for ( int i1 = 1 ; i1 < N ; i1++) for ( int i2 = 1 ; i2 < N ; i2++) { ms(vis,false); for ( int j1 = 0 ; j1 < i1 ; j1++) for ( int j2 = 0 ; j2 < i2 ; j2++) vis[sg[i1][j2]^sg[j1][i2]] = true; //注意sg函数的变化规则。。其实是把一次爆炸考虑成两个爆炸的叠加，所以异或了。 for ( int k = 0 ; ; k++) if (!vis[k]) { sg[i1][i2] = k; break; } } } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif sg_init(); //or ( int i = 0 ; i <= 10 ; i++) // for ( int j = 0 ; j <= 10 ; j++) //cout<<"i:"<<i<<" j:"<<j<<" sgg[i][j]:"<<sg[i][j]<<endl; while (~scanf("%d%d",&n,&m)) { if (n==0&&m==0) break; for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]); int sum = 0 ; for ( int i = 0 ; i < n ; i++) for ( int j = 0 ; j < m ; j++) if (maze[i][j]=='#') { int tmp = sg[i][j]; sum ^= tmp; } if (sum) { puts("John"); } else { puts("Jack"); } } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！