HDOJ 2147 kiki’s game

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2147


这题~~~规律流~~~
分析如下:
引用了MiYu的:http://www.cnblogs.com/MiYu/archive/2010/08/18/1802685.html

P点:就是P个石子的时候,对方拿可以赢(自己输的)

N点:就是N个石子的时候,自己拿可以赢

现在关于P,N的求解有三个规则

(1):最终态都是P

(2):按照游戏规则,到达当前态的前态都是N的话,当前态是P

(3):按照游戏规则,到达当前态的前态至少有一个P的话,当前态是N

题意:

在一个m*n的棋盘内,从(1,m)点出发,每次可以进行的移动是:左移一,下移一,左下移一。然后kiki每次先走,判断kiki时候会赢(对方无路可走的时候)。

我们可以把PN状态的点描绘出来:

HDOJ 2147

这些点的描绘有一个程序:

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
#include<iostream>
using namespace std;
bool map[2001][2001];//1 P 0 N;
int main(){
       int i,j,k;
       map[1][1]=1;
       for(i=2;i<=2000;i++)
       {
              if(map[i-1][1])
                     map[i][1]=0;
              else map[i][1]=1;
              for(j=2;j<i;j++){
                     if(!map[i][j-1]&&!map[i-1][j-1]&&!map[i-1][j])
                            map[i][j]=1;
                     else map[i][j]=0;
              }
              if(map[1][i-1])
                     map[1][i]=0;
              else map[1][i]=1;
              for(j=2;j<i;j++){
                     if(!map[j-1][i]&&!map[j-1][i-1]&&!map[j][i-1])
                            map[j][i]=1;
                     else map[j][i]=0;
              }
              if(!map[i][i-1]&&!map[i-1][i-1]&&!map[i-1][i])
                     map[i][i]=1;
              else map[i][i]=0;
       }
       int M,N;
       for(i=1;i<=10;i++){
              for(j=1;j<=10;j++)
                     printf("%c ",map[i][j]?'P':'N');
              printf("\n");
       }
       while(scanf("%d%d",&M,&N)&&M&&N){
              if(map[M][N]) printf("What a pity!\n");
              else printf("Wonderful!\n");
       }
       return 0;
}

AC代码:

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main ()
{
    int n,m;
    while ( cin >> n >> m , n + m )
    {
          puts ( n%2 && m % 2 ? "What a pity!" : "Wonderful!"); 
    }
    return 0; 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2147 kiki’s game》有5,571个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注