HDOJ1760

发表于 | 分类于

题目链接:HDOJ 1760

题意：给你一个棋盘 铺板砖 板砖大小2x2 铺过的地方不能再铺，棋盘标记1的地方也不能铺
PS：不要吐槽为什么我拿板砖类比

很显然这是一个博弈题 还是个二维博弈
使用dfs判断各个位置的SG值
for example,sample input 2:

4 4
0000
0010
0100
0000

显然 左上角四块和右下角四块可以放砖
我们先求 先放左上角四块是否是必胜的
即求：

1100
1110
0100
0000

是否是必败点
即求：

1100
1110
0111
0011

是否是必胜点
显然这个点没砖可放 这个点是必败点
所以先放左上角四块是必败点
同理先放左下角四块也是必败的
所以初始状态lele一定是输的 输出No

根据叙述 我们写出dfs函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline bool dfs(){
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=m-1;j++){
            if(!pp[i][j]&&!pp[i+1][j]&&!pp[i][j+1]&&!pp[i+1][j+1]) {
                pp[i][j]=pp[i][j+1]=pp[i+1][j]=pp[i+1][j+1]=1;
                if(!dfs()) {
                    pp[i][j]=pp[i][j+1]=pp[i+1][j]=pp[i+1][j+1]=0;
                    return true;
                }
                pp[i][j]=pp[i][j+1]=pp[i+1][j]=pp[i+1][j+1]=0;
            }
        }
    }
    return false;
}

如果当前状态是是必败点 dfs返回false
否则 返回true
要注意dfs在搜索下一个状态的时候 要把放的那四个格子置1 回溯的时候置0
其他没啥问题了
代码：

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
41
42
43
44
45
#include<bits/stdc++.h>

using namespace std;

bool pp[55][55];
int n,m;

inline bool dfs(){
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=m-1;j++){
            if(!pp[i][j]&&!pp[i+1][j]&&!pp[i][j+1]&&!pp[i+1][j+1]) {
                pp[i][j]=pp[i][j+1]=pp[i+1][j]=pp[i+1][j+1]=1;
                if(!dfs()) {
                    pp[i][j]=pp[i][j+1]=pp[i+1][j]=pp[i+1][j+1]=0;
                    return true;
                }
                pp[i][j]=pp[i][j+1]=pp[i+1][j]=pp[i+1][j+1]=0;
            }
        }
    }
    return false;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("input.in","r",stdin);
    // freopen("output.o","w+",stdout);
    // #endif
    // int begin_time=clock();
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                char buf;
                cin>>buf;
                pp[i][j]=(buf=='0')?0:1;
            }
        }
        if(dfs()) puts("Yes");
        else puts("No");
    }
    // cout<<"time use: "<<clock()-begin_time<<" ms"<<endl;
    return 0;
}