（博弈 sg入门）kiki's game -- hdu -- 2147

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2147

题意：

    在一个n*m的棋盘上，从  （1,m），即右上角开始向左下角走。

       下棋者只能往左边(left)，左下面(left-underneath)，下面(underneath)，这三个方格下棋。

最后不能移动的人算输 

思路： 
手动可以画出必胜态以及必败态的图 
可以很容易 找出规律 

(1) 所有终结点是必败点（P点）；

  (2)从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）；

  (3)无论如何操作，从必败点（P点）都只能进入必胜点（N点）.

由此可知 10*10之内的为   （完全可以手写出来） 

NNNNNNNNNN 
PNPNPNPNPN 
NNNNNNNNNN 
PNPNPNPNPN 
NNNNNNNNNN 
PNPNPNPNPN 
NNNNNNNNNN 
PNPNPNPNPN 
NNNNNNNNNN 
PNPNPNPNPN

可以看出  NN

                  PN  这样的规律    之后很容易知道怎么做了   

 

代码：

#include<stdio.h>
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)break;
        if(n%2==1&&m%2==1)printf("What a pity!\n");
        else printf("Wonderful!\n");
    }
    return 0;
}

还可以用SG函数打表找出我们所要的结果NP 图

 

#include<stdio.h>
#include<string.h>
const int sz=200;
int SG[sz][sz];
int dir[3][2]={-1,0,0,1,-1,1};
int n,m;
void get_sg()
{
    int i,j;
    memset(SG,0,sizeof(SG));
      for(i=n;i>=1;i--)
        for(j=1;j<=m;j++)
      {
          if(!SG[i][j])
            for(int k=0;k<3;k++)
            {
              int xx=i+dir[k][0];
              int yy=j+dir[k][1];
               if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
               {
                SG[xx][yy]=1;
               }
            }
      }
}
int main()
{
    int i,j;

    while(scanf("%d %d",&n,&m)!=EOF)
    {
        get_sg();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++) if(SG[i][j]==1) printf("N"); else printf("P");
            printf("\n");
        }
        if(SG[1][m]==1)
        {
            printf("Wonderful!\n");
        }
        else printf("What a pity!\n");
    }
    return 0;
}