LCP 58. 积木拼接

本文最后更新于:2022年5月14日 下午

https://leetcode.cn/problems/De4qBB/

这个题目比较困难的地方就是记录方阵的翻转、旋转状态

方阵的翻转,旋转和转置模板

为了能够高效的表示当前方阵的状态,我们用方阵的四个角点表示方阵当前的状态。

比如一个3×33 \times 3的方阵,我们用array<pair<int, int>, 4>来存放这个方阵的四个角,依次分别是:左上角(0,0)(0, 0)、右上角(0,y)(0, y)、左下角(x,0)(x, 0)和右下角(x,y)(x, y)

翻转操作

1
2
3
110    上下进行翻转    000
010 -------------> 010
000 110

那么他四个点的坐标就是

1
2
3
(0,0)  (0,3)      上下进行翻转      (3,0)  (3,3) 
------------->
(3,0) (3,3) (0,0) (0,3)

对应代码:

1
2
3
4
5
6
7
8
9
10
11
void mirror(int dr = 1){
if(dr == 1){
// 左右翻转
swap(vec[0], vec[1]);
swap(vec[2], vec[3]);
}else{
// 上下翻转
swap(vec[0], vec[2]);
swap(vec[1], vec[3]);
}
}

转置操作

1
2
3
110      转置方阵     100
010 -------------> 110
000 000

那么他四个点的坐标就是

1
2
3
(0,0)  (0,3)        转置方阵       (0,0)  (3,0) 
------------->
(3,0) (3,3) (0,3) (3,3)

对应代码:

1
2
3
4
5
6
7
8
9
void transpose(int dr = 1){
if(dr == 1){
// 沿着y = x 翻转
swap(vec[1], vec[2]);
}else{
// 沿着x + y = n 翻转
swap(vec[0], vec[3]);
}
}

旋转操作

1
2
3
110   顺时针旋转90001
010 -------------> 011
000 000

那么他四个点的坐标就是

1
2
3
(0,0)  (0,3)     顺时针旋转90(3,0)  (0,0) 
------------->
(3,0) (3,3) (3,3) (0,3)

对应代码(旋转可以用转置+翻转来实现):

1
2
3
4
5
6
7
8
9
10
void rotate(int dr = 1){
transpose();
if(dr == 1){
// 顺时针
mirror(1);
}else{
// 逆时针
mirror(0);
}
}

可以从上面看出来,对图形的操作,就可以表示为对四个角的二维方阵的操作。

因为翻转之后,我们需要知道新的图形的x,y的坐标轴的变化,比如

1
2
3
(0,0)  (0,3)     顺时针旋转90(3,0)  (0,0) 
------------->
(3,0) (3,3) (3,3) (0,3)

这个图形旋转之前的坐标轴的单位变化分别是dx=(1,0)dx = (1, 0)dy=(0,1)dy = (0, 1),顺时针旋转90度之后的单位变化dx=(0,1)dx = (0, 1)dy=(1,0)dy = (-1, 0)
为了方便记录当前的单位变化dxdxdydy,我们在每次翻转、旋转和转置的时候,重新计算一次dxdxdydy。计算的代码如下:

1
2
3
4
5
6
7
void update(){
int xlim = abs(vec[2].first - vec[0].first) + abs(vec[2].second - vec[0].second);
int ylim = abs(vec[1].first - vec[0].first) + abs(vec[1].second - vec[0].second);
assert(xlim > 0 and ylim > 0);
dx = Point{(vec[2].first - vec[0].first) / xlim, (vec[2].second - vec[0].second) / xlim};
dy = Point{(vec[1].first - vec[0].first) / ylim, (vec[1].second - vec[0].second) / ylim};
}

那么最终,我们就可以通过左上角的坐标,和单位坐标的变化dxdxdydy,来映射得到原始的坐标。
代码如下所示:

1
2
3
Point mapping(Point p){
return {vec[0].first + dx.first * p.first + dy.first * p.second, vec[0].second + dx.second * p.first + dy.second * p.second};
}

那么最终完整的矩阵模板:

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
class Rectangle{
public:
typedef pair<int, int> Point;
Rectangle(int sx, int sy) : dx({1, 0}), dy({0, 1}), vec({Point{0, 0}, Point{0, sy - 1}, Point{sx - 1, 0}, Point{sx - 1, sy - 1}}){}
void mirror(int dr = 1){
if(dr == 1){
// 左右翻转
swap(vec[0], vec[1]);
swap(vec[2], vec[3]);
}else{
// 上下翻转
swap(vec[0], vec[2]);
swap(vec[1], vec[3]);
}
update();
}
void transpose(int dr = 1){
if(dr == 1){
// 沿着y = x 翻转
swap(vec[1], vec[2]);
}else{
// 沿着x + y = n 翻转
swap(vec[0], vec[3]);
}
update();
}
void rotate(int dr = 1){
transpose();
if(dr == 1){
// 顺时针
mirror(1);
}else{
// 逆时针
mirror(0);
}
update();
}
Point mapping(Point p){
return {vec[0].first + dx.first * p.first + dy.first * p.second, vec[0].second + dx.second * p.first + dy.second * p.second};
}
// 当前状态下,x轴的方向和y轴的方向
Point dx, dy;
// 当前状态下的方阵四个角点的坐标
array<Point, 4> vec;
private:
void update(){
int xlim = abs(vec[2].first - vec[0].first) + abs(vec[2].second - vec[0].second);
int ylim = abs(vec[1].first - vec[0].first) + abs(vec[1].second - vec[0].second);
assert(xlim > 0 and ylim > 0);
dx = Point{(vec[2].first - vec[0].first) / xlim, (vec[2].second - vec[0].second) / xlim};
dy = Point{(vec[1].first - vec[0].first) / ylim, (vec[1].second - vec[0].second) / ylim};
}

};

本题的实现

前置内容

我们首先设计了6个位置,就是立方体的展开图。如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
      00000             
00000
00000
00000
00000

11111 22222 33333 44444
11111 22222 33333 44444
11111 22222 33333 44444
11111 22222 33333 44444
11111 22222 33333 44444

55555
55555
55555
55555
55555

我们把位置按照这个形状进行设计,是因为可以和方便的计算他的相邻边。具体可看后面相邻边的数字变化。

然后定义每个矩阵的边的顺序【0,1,2,3】,依次是【上,右,下,左】。
比如0号位置的下方和2号位置的上方相邻,就构成一个边的四元组「0号位置,2号位置,下方,上方」,[0, 2, 2, 0]。
比如0号位置的左边和1号位置的上方相邻,就构成一个边的四元组「0号位置,1号位置,左边,上方」,[0, 1, 3, 0]。

那么写出0号位置所相邻边的四元组:

1
2
3
4
[0, 1, 3, 0]
[0, 2, 2, 0]
[0, 3, 1, 0]
[0, 4, 0, 0]

然后是5号位置相邻边的四元组:

1
2
3
4
[5, 1, 0, 2]
[5, 2, 1, 2]
[5, 3, 2, 2]
[5, 4, 3, 2]

然后就是其他四条边:

1
2
3
4
[1, 2, 1, 3]
[2, 3, 1, 3]
[3, 4, 1, 3]
[4, 1, 1, 3]

为了按照顺序获取方阵的四条边,我们先定义了个方阵,然后逆时针旋转四次,每次旋转,获取一次当前位置的第一条边。

1
2
3
4
5
6
Rectangle rec(sz, sz);
vector<Rectangle> recd;
for(int i = 0; i < 4; ++i){
recd.push_back(rec);
rec.rotate(0);
}

题目思路

我们本题使用搜索检查每个位置是否满足。首先固定第一个方阵,我们把它固定放在0位置。然后每个位置尝试将其他的方阵旋转或者翻转放入。
对于立体图形的边,我们要求不能相邻的边在同一个位置具有相同的元素。
对于立体图形的角,我们要求不能两个边同时出现11,为了避免三个相邻面共享的同一个角都是0,我们一开始就先计算1个总个数,要求1个总个数刚刚好。
完整代码如下:

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
class Rectangle{
public:
typedef pair<int, int> Point;
Rectangle(int sx, int sy) : dx({1, 0}), dy({0, 1}), vec({Point{0, 0}, Point{0, sy - 1}, Point{sx - 1, 0}, Point{sx - 1, sy - 1}}){}
void mirror(int dr = 1){
if(dr == 1){
// 沿着x轴翻转
swap(vec[0], vec[1]);
swap(vec[2], vec[3]);
}else{
// 沿着y轴翻转
swap(vec[0], vec[2]);
swap(vec[1], vec[3]);
}
update();
}
void transpose(int dr = 1){
if(dr == 1){
// 沿着y = x 翻转
swap(vec[1], vec[2]);
}else{
// 沿着x + y = n 翻转
swap(vec[0], vec[3]);
}
update();
}
void rotate(int dr = 1){
transpose();
if(dr == 1){
// 顺时针
mirror(1);
}else{
// 逆时针
mirror(0);
}
update();
}
Point mapping(Point p){
return {vec[0].first + dx.first * p.first + dy.first * p.second, vec[0].second + dx.second * p.first + dy.second * p.second};
}
Point dx, dy;
array<Point, 4> vec;
private:
void update(){
int xlim = abs(vec[2].first - vec[0].first) + abs(vec[2].second - vec[0].second);
int ylim = abs(vec[1].first - vec[0].first) + abs(vec[1].second - vec[0].second);
assert(xlim > 0 and ylim > 0);
dx = Point{(vec[2].first - vec[0].first) / xlim, (vec[2].second - vec[0].second) / xlim};
dy = Point{(vec[1].first - vec[0].first) / ylim, (vec[1].second - vec[0].second) / ylim};
}

};
class Solution {
public:
bool composeCube(vector<vector<string>>& shapes) {
int sz = shapes[0].size();
int cnt = sz * sz * 2 + (sz - 1) * (sz - 2) * 4;
for(auto& vec: shapes) {
for(auto& row: vec){
for(auto& c: row){
if(c == '1') --cnt;
}
}
}
if(cnt != 0) return false;
typedef Rectangle::Point Point;
Rectangle rec(sz, sz);
vector<Rectangle> recd;
for(int i = 0; i < 4; ++i){
recd.push_back(rec);
//recd.back().debug();
rec.rotate(0);
}
vector<Rectangle> recs(6, Rectangle{sz, sz});
auto&& isCon = [&](int x, int y, int sx, int sy){
for(int i = 0; i < sz; ++i){
auto px = recd[sx].mapping({0, i});
auto py = recd[sy].mapping({0, sz - 1 - i});
auto ppx = recs[x].mapping(px);
auto ppy = recs[y].mapping(py);
if(i == 0 or i == sz - 1){
if(shapes[x][ppx.first][ppx.second] == shapes[y][ppy.first][ppy.second] and shapes[y][ppy.first][ppy.second] == '1'){
return false;
}
}else if(shapes[x][ppx.first][ppx.second] == shapes[y][ppy.first][ppy.second]){
return false;
}
}
return true;
};
auto&& show = [&](int i, int x, int y){
return recs[i].mapping({x, y});
};
vector<int> idx(6);
vector<vector<int>> dr = {{-1, 0, -1, -1}, {1, 2, 3, 4}, {5, -1, -1, -1}};
auto&& print = [&](int q){
for(int i = 0; i < 3; ++i){
for(int j = 0; j < sz; ++j){
for(int k = 0; k < 4; ++k){
for(int l = 0; l < sz; ++l){
if(dr[i][k] < 0) cout << " ";
else if(dr[i][k] > q) cout << "?";
else{
auto rt = show(idx[dr[i][k]], j, l);
cout << shapes[idx[dr[i][k]]][rt.first][rt.second];
}
}
cout << " ";
}
cout << endl;
}
cout << endl;
}
};
auto&& check = [&](int sz){

bool ok = true;
for(int i = 0; i < 4 and i + 1 <= sz and ok; ++i){
if(!isCon(idx[0], idx[i + 1], 3 - i, 0)){
ok = false;
}
}
for(int i = 0; i < 4 and i + 1 <= sz and (i + 1) % 4 + 1 <= sz and ok; ++i){
if(!isCon(idx[i + 1], idx[(i + 1) % 4 + 1], 1, 3)) ok = false;
}
if(sz == 5){
for(int i = 0; i < 4 and ok; ++i){
if(!isCon(idx[5], idx[i + 1], i, 2)) ok = false;
}
}

// if(ok){
// print(sz);
// cout << "ok" << endl;
// }

return ok;
};
idx[0] = 0;
vector<int> vis(6, 0);
vis[0] = 1;
auto&& dfs = [&](auto&& self, int cur) -> bool{
if(cur >= 6) {
return true;
}
for(int i = 1; i < 6; ++i){
if(vis[i] == 0){
idx[cur] = i;
vis[i] = 1;
for(int m = 0; m < 2; ++m){
for(int r = 0; r < 4; ++r){
if(check(cur)) {
if(self(self, cur + 1)) return true;
}
recs[i].rotate();
}
recs[i].mirror();
}
vis[i] = 0;
}
}
return false;
};
if(dfs(dfs, 1)) return true;
recs[0].mirror();
if(dfs(dfs, 1)) return true;
return false;
}
};

最后打印一下第一个样例的匹配情况:

1
2
3
4
5
6
7
8
9
10
11
12
// 样例1
000
110
000

001 011 011 011
011 010 110 111
010 000 011 011

001
011
001

LCP 58. 积木拼接
https://dianhsu.top/2022/05/13/LCP58/
作者
Dian Hsu
发布于
2022年5月13日
许可协议