hdu 1760 DFS+博弈

0代表可放 1带表不能放每次放一个2*2的方块不能放者败
如果先手必胜则输出Yes

必胜态：从当前状态所能到达的状态中存在一个必败态
必败态：从当前状态所能达到的状态全部是必胜态

Sample Input
4 4
0000
0000
0000
0000
4 4
0000
0010
0100
0000

Sample Output
Yes
No

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <string>
 6 # include <cmath>
 7 # include <queue>
 8 # include <list>
 9 # define LL long long
10 using namespace std ;
11 
12 char str[50][50];
13 int p[50][50];
14 int n,m;
15 int dfs()
16 {
17     int i,j,flag;
18     flag = 0;
19     for(i = 0;i < n-1;i ++)
20     {
21         for(j = 0;j < m-1;j ++)
22         {
23             if(p[i][j] == 0&&p[i+1][j] == 0&&p[i][j+1] == 0&&p[i+1][j+1] == 0)
24             {
25                 p[i][j] = p[i+1][j] = p[i][j+1] = p[i+1][j+1] = 1;
26                 if(dfs() == 0) //子状态存在必败态
27                 flag = 1;
28                 p[i][j] = p[i+1][j] = p[i][j+1] = p[i+1][j+1] = 0;
29             }
30         }
31     }
32     if(flag)
33     return 1;
34     else
35     return 0;
36 }
37 int main()
38 {
39     int i,j;
40     while(scanf("%d%d",&n,&m)!=EOF)
41     {
42         for(i = 0; i < n; i ++)
43             scanf("%s",str[i]);
44         for(i = 0; i < n; i ++)
45         {
46             for(j = 0; j < m; j ++)
47             {
48                 if(str[i][j] == '0')
49                 p[i][j] = 0;
50                 else
51                 p[i][j] = 1;
52             }
53         }
54         if(dfs())
55         printf("Yes
");
56         else
57         printf("No
");
58     }
59     return 0;
60 }

View Code