HDOJ 5754 Life Winner Go
很好的一个博弈论的题！多校训练还是挺有意义的，贴个链接：HDOJ5754
不多说了，开始分析！
博弈论做题原则：打表
打表原理：必胜状态是其状态前一步的集合之中存在必败态；必败态是其状态前一步的集合之中都是必胜态
很简单的道理：想要赢的话，就是上一步别人给了你赢的机会，也就是别人走到了一个必败态；而只能输的情况，就是上一步不管怎么走，别人都是必胜的状态
分类是很容易的，根据棋子的走法分类，也就是题目中的1,2,3,4
注意每个棋子的走法方向题目中强调了只能往右下角
第一类：king
横直斜走均可，但每次只能走一格
用（1,1）举例，下一步可以到的方向是（1,2），（2,2），（2,1）
所以开始打表，先处理好边界：（1,1）必败；（1,2）只能由（1,1）过来，必胜；（1,3）只能由（1,2）过来，必败；（1,4）只能由（1,3）过来，必胜……这个是第一行；
同理，第一列，也是一样
下面给出打表程序：
int n=10,m=10;
for(int i=0;i<=n;i++) mp[i][0]=1;
for(int j=0;j<=m;j++) mp[0][j]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if (mp[i-1][j-1]==0||mp[i-1][j]==0||mp[i][j-1]==0) mp[i][j]=1;
else mp[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",mp[i][j],j==n?'\n':' ');把n和m的值定义小一点，就可以把表格打出来，找规律呗，输出后的结果如下：
0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1看到规律了吧，输入的n和m都是奇数的话，先手必败；否则先手必胜
第二类：rook（castle）
车的走法是：走横纵向，可以走任意格。（1,1）举例，可以走到（1,2），（1,3）……（1，m），（2,1），（3,1）……（n，1）
这个就没办法打表了，因为转移的可能太多，无法枚举
再说说博弈论怎么判断输赢：如果你一直可以把“不利”的状态留给别人，你就可以赢
什么叫做不利的状态？完全对称的状态。
因为在完全对称的情况下，先手必败。在相同的棋子移动的规则下，先手移动之后，必然打破对称的平衡；而后手在行动的时候，唯一的必胜策略就是把局面再次变成对称的情况，也就是选择先手未移动的方向，走与先手相同的步数，达到对称的平衡
这种文字说法可能有点绕，举例子吧：n=m=5
先手从（1,1）出发，达到（5,5）为获胜
因为横向的距离为4，纵向的距离为4，横向的距离和纵向相等，所以后手获胜
无论先手选择横向走a格，还是纵向走b格，后手的必胜策略是纵向走a格，或横向走b格
使得在一轮行动之后，到达了（a，a）或者（b，b）点，与（1,1）没有本质区别
那么，先手怎么样获胜呢？只能祈祷n和m不相等
如果n大于m，那么先手在纵向走n-m格，使得横向和纵向都剩下m格
如果m大于n，那么后手在纵向走m-n格，使得横向和纵向都剩下n格
第三类：knight
这个题最难想到的是这个点！马的走法是走日字，右下角，那么从（1,1）可以达到的点是（2,3），（3,2）
同上面的做法，先打表，是吧，把马所有可以达到的点全部打表出来，一个BFS，因为矩阵最大是1000*1000，可以存下来
void getmap(){
memset(mp,0,sizeof(mp));
mp[1][1]=1;
queue<node> q;
while(!q.empty()) q.pop();
u.x=1;u.y=1;
q.push(u);
while(!q.empty()){
u=q.front();q.pop();
v.x=u.x+1;
v.y=u.y+2;
if (mp[v.x][v.y]==0&&v.x<=1000&&v.y<=1000){
mp[v.x][v.y]=mp[u.x][u.y]+1;
q.push(v);
}
v.x=u.x+2;
v.y=u.y+1;
if (mp[v.x][v.y]==0&&v.x<=1000&&v.y<=1000){
mp[v.x][v.y]=mp[u.x][u.y]+1;
q.push(v);
}
}
for(int i=1;i<=15;i++)
for(int j=1;j<=15;j++)
printf("%3d%c",mp[i][j],j==15?'\n':' ');
}表格如下：
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0 0 0 0 0 0
0 2 0 0 3 0 0 0 0 0 0 0 0 0 0
0 0 0 3 0 0 4 0 0 0 0 0 0 0 0
0 0 3 0 0 4 0 0 5 0 0 0 0 0 0
0 0 0 0 4 0 0 5 0 0 6 0 0 0 0
0 0 0 4 0 0 5 0 0 6 0 0 7 0 0
0 0 0 0 0 5 0 0 6 0 0 7 0 0 8
0 0 0 0 5 0 0 6 0 0 7 0 0 8 0
0 0 0 0 0 0 6 0 0 7 0 0 8 0 0
0 0 0 0 0 6 0 0 7 0 0 8 0 0 9
0 0 0 0 0 0 0 7 0 0 8 0 0 9 0
0 0 0 0 0 0 7 0 0 8 0 0 9 0 0
0 0 0 0 0 0 0 0 8 0 0 9 0 0 10
0 0 0 0 0 0 0 8 0 0 9 0 0 10 0所以，表格中的奇数为先手必败，偶数（除了0）为先手必胜，0为平局？
这种想法是打表想法，但是，没有理解博弈论的精髓：每个玩家在选择的时候，一定会选择对自己最有利的选择！
拿几个点举例子：
（3,5）和（5,3）这个3的点
（3,5）是平局！为什么，因为先手不会傻到走到（2,3），这样后手赢！所以先手的最好策略是走到（3,2）！这样后手无棋可走，只能平局
（5,3）同理！是平局，而不是后手胜
（4,4）这个3的点，是后手必胜
因为无论先手走到（2,3）还是（3,2），这两个点都是必败点，后手一步就能够到了
所以，这种情况的解法是：看对称性！
首先判断能不能到，因为马每次走的方向虽然不同，但是横向和纵向方向上走的步数和是固定的3
原来在（1,1），所以n+m的值对3取余一定为2，也就是（n+m）%3==2，否则不可能能够到，一定为平局
然后呢，如果n=m，那么就是与（2）相同的对称类型，一定后手获胜，策略是与先手走“相反”的方向，也就是先手选择（1,2）的方向，那么后手选择（2,1）
如果n！=m，那么判断max（n，m）-2是不是等于min（n，m）-1
这个条件什么意思？也是对称！先手可以选择（1,2）或者（2,1）的走法，是不是可以让局面变得对称！
看完这段分析如果觉得绕，talk is free，show me your code！
else if (op==3){
if ((n+m)%3==2){
if (n==m) puts("G");
else{
if(n<m) swap(n,m);
n-=2;
m-=1;
if (n==m) puts("B");
else puts("D");
}
}
else puts("D");
}第四类：queen，也是一个很麻烦的情况，不过有两种处理方法
走的规则是横纵斜，可以任意格，举例n=m=5，从（1,1）出发，可以达到的点是（1,2），（1,3），（1,4），（1,5），（2,1），（3,1），（4,1），（5,1），（2,2），（3,3），（4,4），（5,5）
所以，先打表看规律：这个打表只能手动推理了
方法跟前面解释的一样，不多说，得到结论：
2 3
4 6
5 8
7 11
9 14
10 16
12 19每个数字只出现一次，两个数字的差值是1,2,3,4,5,……跟行数有关，那么，打表啊！
void getmap2(){
memset(wa,0,sizeof(wa));
bool num[maxn];
memset(num,false,sizeof(num));
wa[2][3]=1;
int addnum=1;
num[2]=num[3]=true;
//printf("2 3\n");
int minnum=4;
while(1){
while(num[minnum]==true) minnum++;
addnum++;
if (minnum+addnum>=maxn) break;
num[minnum]=num[minnum+addnum]=true;
//printf("%d %d\n",minnum,minnum+addnum);
wa[minnum][minnum+addnum]=true;
minnum++;
}
}弄成一个判断数组就好了！暴力搞出来
其实，看到先手必败态的规律了吧：那就是威佐夫博弈的结论啊！
结论判断代码，当然也可以打表直接用
n--;m--;
int delta = n-m;
if (m == (int)(delta*(sqrt(5)+1)/2)) puts("G");
else puts("B");分析了所有的情况了，用if和else if可以完美过此题！
一个很好的博弈论的题！
