zoj 3513 Human or Pig 博弈论

思路：P态的所有后继全为H态，第一个格子为P态，第一行和第一列为H态。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<set>
 7 #include<vector>
 8 #define ll long long
 9 #define M 80004
10 #define inf 1e10
11 #define mod 1000000007
12 using namespace std;
13 int m,n;
14 char ans[M];
15 int cal(int x,int y)
16 {
17     return x*m+y;
18 }
19 char dfs(int x,int y)
20 {
21     int ret = cal(x,y);
22     if(ans[ret]!='#') return ans[ret];
23     if(!x||!y) return ans[ret]='H';
24     char c='P';
25     for(int i=1;x>i*y;i++)
26     if(dfs(x-i*y,y)=='P'){
27         c='H';
28         break;
29     }
30     for(int i=1;y>i*x;i++)
31     if(dfs(x,y-i*x)=='P'){
32         c='H';
33         break;
34     }
35     return ans[ret]=c;
36 }
37 int main()
38 {
39     int i,j,ca=0;
40     while(scanf("%d%d",&n,&m)!=EOF){
41         printf("Case #%d:
",++ca);
42         memset(ans,'#',sizeof(ans));
43         ans[1]='P';
44         for(i=1;i<=n;i++){
45             for(j=1;j<=m;j++)
46                 putchar(dfs(i,j));
47             puts("");
48         }
49     }
50     return 0;
51 }

View Code