【题解】第八届蓝桥杯（国赛）·瓷砖样式·C/C++·DFS（中转点）_c++瓷砖问题

爱情到来绝不能犹豫。
关注博主容不得迟缓。

算法标签：DFS

题目：

解析：

本题目数据量不大，可以使用DFS枚举每一个砖块的摆放方案来计算。

设MAX_M代表行。MAX_N代表列。

MAP代表墙壁（没贴瓷砖之前的墙壁）。当MAP的某一点的值是-1，意味着可以从这里放瓷砖，因为这一点没有被染色。MAP初始化为-1，不能走的地方为-2。颜色为0和1。

放瓷砖的方向有两种。

设（x，y）表示MAP的某一点。

（1）从这点开始，横着放。那么（x，y）和（x，y+1）都被染色成Color。
（2）从这点开始，竖着放。那么（x，y）和（x+1，y）都被染色成Color。

当然了，染色之前需要判断，从这个点开始，到底能不能横着摆放，或者说竖着摆放。如果这个点不支持摆放，那么直接return即可。不用往下搜索了。

根据以上分析，我们有了一个dfs函数。定义如下：

函数dfs的定义：

void dfs(int x, int y, int color, int direct, int num)
1

x和y：代表我们的dfs现在搜索到了哪一个点。

color：代表着map[x][y]这个点现在我们要染上什么颜色。

direct：代表到底是横着放，还是竖着放。

num：代表现在摆放的是第几块砖。

本层次的染色：

在染色之前先判断能不能染色。如果不能染色就直接return。

按照direct的数值和color的数值，染色对应的方块。
// Direct = 0 横着 Direct = 1 竖着 放

    if (direct == 0 && (map[x][y + 1] != -1)) {  //横着放总会出现一点问题，这是因为下一个方块会挡住，这个时候直接回溯。
        return;
    }

    if (direct == 1 && (map[x + 1][y] != -1)) {  //竖着放如果出现问题，也不要往下去做了。
        return;
    }
    
    if (direct == 0) {
        map[x][y] = map[x][y + 1] = color;
    } else if (direct == 1) {
        map[x][y] = map[x + 1][y] = color;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

染色完成之后，如果退出本层次，别忘记回溯，将染色的方块抹去。

    if (direct == 0) {  //回溯
        map[x][y] = map[x][y + 1] = -1;
    } else if (direct == 1) {
        map[x][y] = map[x + 1][y] = -1;
    }
1
2
3
4
5

下一层次的转移（dfs的下一层）：

如果本砖块就是最后一块，那么就不用查找下一层（下一个）砖块的位置了。

如果砖块不是最后一个砖块，就直接无脑搜索就可以啦！

我们的搜索方向就是，（x，y）->（x，y+1）。

这是因为，我们是按行搜索，当行不能搜索，我们就用**“中转点**”将（直到找到可以染色方块的那一个点（下一行））和我们现在的这个点做一个连接。

    if (num == (MAX_N * MAX_M) / 2) {
        // PrintMAP();
        CheckAns();
    } else {  //如果不是最后一个瓷砖，就继续搜索
        //横着放
        dfs(x, y + 1, 0, 0, num + 1);
        dfs(x, y + 1, 1, 0, num + 1);
        //竖着放
        dfs(x, y + 1, 0, 1, num + 1);
        dfs(x, y + 1, 1, 1, num + 1);
    }

1
2
3
4
5
6
7
8
9
10
11
12

中转点的设计：

我们怎么去扩展下一个点呢？
我们利用dfs不停的寻找一个合适的点。
例如上图，绿色方块是我们现在搜索到的位置。
绿色箭头指向我们想要“下一层”拓展的位置。（2，3）。
此时我们先从（2，1）搜索到了（2，2）。发现（2，2）是一个中转点。于是又从（2，2）搜索到了（2，3）。发现（2，3）是我们要染色的点。

再如上图，上面“橙色”圆圈里面的数字意味着扩展的顺序，我们扩展先从（2，4）发现不能染色，所以中转为（3，1）又不能染色，最终中转为（3，2）可以染色。

    if (map[x][y] != -1) {  //说明这个点是染过颜色或者是墙壁，是：过渡点（“中转点”）
        if (y >= MAX_N) {
            dfs(x + 1, 1, color, direct, num);  //仅仅只是将状态转移，自己这里什么都不做。
        } else {
            dfs(x, y + 1, color, direct, num);
        }
        return;  //使命完成了，直接退出这个点就好。这个点就是“中转点”。
    }
1
2
3
4
5
6
7
8

请仔细阅读上面的代码，体会“中转”的思想。
注意dfs的color和direct和num什么都没有变，因为仅仅只是一个“传递”。

地图判定：

对于一个2X2的地图，如果把地图里面的染色（0和1）加起来MOD 4是0的话，意味着这个地图是全部同色的。不满足题目要求。

注意本题目还有一个地方是：不要求缝隙，之要求颜色。

注意观察（1）（2）两种方案的瓷砖的缝隙是不同的，但是他们最终的染色结果确实一样的。所以（1）和（2）是同一种答案。

所以我设计的时候使用了一个set来查重。
具体您可以参考我的代码。过程很直观，并不复杂，不再多言。

感谢您的观看，如果您觉得有意思，您可以点击“关注”按钮来关注我。

正解代码：

dfs核心部分总长43行，不是很长。代码不难。思路也很直观。就是要注意：与缝隙无关，只和颜色有关。

#include <cstring>
#include <iostream>
#include <set>
#include <sstream>
#define MAX_M 3   //行
#define MAX_N 10  //列
using namespace std;
int map[MAX_M + 3][MAX_N + 3];
set<string> SsetAns;
// Direct==0 横着 ===1 竖着 放
// color 只有两种颜色 Num是现在是第几块板子
void PrintMAP() {
    for (int i = 1; i <= MAX_M; i++) {
        for (int j = 1; j <= MAX_N; j++) {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool PANDUAN() {
    for (int i = 1; i <= MAX_M - 1; i += 1) {
        for (int j = 1; j <= MAX_N - 1; j += 1) {
            if (map[i][j] == -1 || map[i + 1][j] == -1 || map[i][j + 1] == -1 || map[i + 1][j + 1] == -1)
                return false;
            if ((map[i][j] + map[i + 1][j] + map[i][j + 1] + map[i + 1][j + 1]) % 4 == 0)
                return false;
        }
    }
    return true;
}

void CheckAns() {
    string st = "";
    if (PANDUAN()) {
        for (int i = 1; i <= MAX_M; i++) {
            for (int j = 1; j <= MAX_N; j++) {
                st.push_back('0' + map[i][j]);
            }
        }
        SsetAns.insert(st);
    }
}
void dfs(int x, int y, int color, int direct, int num) {
    if (map[x][y] != -1) {  //说明这个点是染过颜色或者是墙壁，是：过渡点（“中转点”）
        if (y >= MAX_N) {
            dfs(x + 1, 1, color, direct, num);  //仅仅只是将状态转移，自己这里什么都不做。
        } else {
            dfs(x, y + 1, color, direct, num);
        }
        return;  //使命完成了，直接退出这个点就好。这个点就是“中转点”。
    }

    if (direct == 0 && (map[x][y + 1] != -1)) {  //横着放总会出现一点问题，这是因为下一个方块会挡住，这个时候直接回溯。
        return;
    }

    if (direct == 1 && (map[x + 1][y] != -1)) {  //竖着放如果出现问题，也不要往下去做了。
        return;
    }

    //开始染色
    if (direct == 0) {
        map[x][y] = map[x][y + 1] = color;
    } else if (direct == 1) {
        map[x][y] = map[x + 1][y] = color;
    }

    if (num == (MAX_N * MAX_M) / 2) {
        // PrintMAP();
        CheckAns();
    } else {  //如果不是最后一个瓷砖，就继续搜索
        //横着放
        dfs(x, y + 1, 0, 0, num + 1);
        dfs(x, y + 1, 1, 0, num + 1);
        //竖着放
        dfs(x, y + 1, 0, 1, num + 1);
        dfs(x, y + 1, 1, 1, num + 1);
    }

    if (direct == 0) {  //回溯
        map[x][y] = map[x][y + 1] = -1;
    } else if (direct == 1) {
        map[x][y] = map[x + 1][y] = -1;
    }
}

void initMAP() {
    memset(map, -1, sizeof(map));           //-1代表这个地图可走。
    for (int i = 0; i <= MAX_N + 1; i++) {  //-2代表地图的边界，不可走。
        map[0][i] = -2;
        map[MAX_M + 1][i] = -2;
    }
    for (int i = 1; i <= MAX_M; i++) {
        map[i][0] = -2;
        map[i][MAX_N + 1] = -2;
    }
}
int main() {
    //第一个砖块放四种情况搜索。
    initMAP();
    dfs(1, 1, 0, 0, 1);
    initMAP();
    dfs(1, 1, 0, 1, 1);
    initMAP();
    dfs(1, 1, 1, 0, 1);
    initMAP();
    dfs(1, 1, 1, 1, 1);
    cout << SsetAns.size() << endl;
    return 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

答案：101466