日历拼图C++解法
0.介绍
任何一个日期都可以用8块拼图拼起来。
如12月3日：
1.思路
主要的思想就是深度优先搜索。
a) 用字符串数组存8种拼图块
|
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
|
char a[9][5][5]={ {{'.','.','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'1','1','1','1'}, {'1','.','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'2','2','2','.'}, {'2','2','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'3','3','.','.'}, {'.','3','3','3'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'4','.','.','.'}, {'4','4','4','.'}, {'.','.','4','.'}, {'.','.','.','.'}}, {{'5','5','5','.'}, {'5','.','.','.'}, {'5','.','.','.'}, {'.','.','.','.'}}, {{'6','6','6','6'}, {'.','6','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'7','7','7','.'}, {'7','7','7','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'8','8','8','.'}, {'8','.','8','.'}, {'.','.','.','.'}, {'.','.','.','.'}}}; |
b) 获得8种拼图块的8种放置方式
这里我使用旋转加翻转实现的。
[2] 最开始为第一个，然后翻转得到第二个。
[3] 再翻转回来，再顺时针90度得到第三个。
重复[2] [3] 步骤就可以得到8种放置方式。
翻转代码
也就是左右交换。
|
1
2
3
4
5
6
|
void filp(char a[5][5]){ for(int i=0;i<4;i++) for(int j=0;j<2;j++){ swap(a[i][j],a[i][3-j]); } } |
旋转代码
这里我是顺时针旋转90度。
|
1
2
3
4
5
6
7
8
9
|
void rot(char a[5][5]){ char b[5][5]; for(int i=0;i<4;i++){ for(int j=0;j<4;j++) b[i][j] = a[3-j][i]; } for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j] = b[i][j];} |
c) 判断某一个位置是否可以放置对应的拼图块。
这里我们以左上角第一个非.的位置为起点，然后进行判断。
|
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
|
bool candown(int x,int y,int i,int j){ int sx = -1, sy = -1; for(int xx=0;xx<4;xx++) for(int yy=0;yy<4;yy++){ if(b[i][j][xx][yy] != '.'){ sx = xx; sy = yy; int kx =sx,ky= sy; while(kx<4 && ky<4){ int nx = x + kx-sx; int ny = y + ky-sy; //如果要覆盖 if(b[i][j][kx][ky]!='.'){ if(nx<0 || ny<0) return false; if(nx<2 && ny<=5){ if(mp[nx][ny]!='.') return false; // mp[nx][ny] = b[i][j][kx][ky]; } else if(nx<=5 && nx>=2 && ny<=6){ if(mp[nx][ny]!='.') return false; // mp[nx][ny] = b[i][j][kx][ky]; } else if(nx==6 && ny<=2){ if(mp[nx][ny]!='.') return false; // mp[nx][ny] = b[i][j][kx][ky]; } else return false; } if(ky==3){ kx++,ky=0; } else ky++; } return true; } } return false;} |
d) 放置拼图块
与第c 步类似。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void down(int x,int y,int i,int j){ for(int xx=0;xx<4;xx++) for(int yy=0;yy<4;yy++){ if(b[i][j][xx][yy] != '.'){ int kx =xx,ky= yy; while(kx<4 && ky<4){ int nx = x + kx-xx; int ny = y + ky-yy; if(b[i][j][kx][ky]!='.'){ mp[nx][ny] = b[i][j][kx][ky]; } if(ky==3){ kx++,ky=0; } else ky++; } return; } } } |
e) 回溯放置
与 d 步类似。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void undown(int x,int y,int i,int j){ for(int xx=0;xx<4;xx++) for(int yy=0;yy<4;yy++){ if(b[i][j][xx][yy] != '.'){ int kx =xx,ky= yy; while(kx<4 && ky<4){ int nx = x + kx-xx; int ny = y + ky-yy; if(b[i][j][kx][ky]!='.'){ mp[nx][ny] = '.'; } if(ky==3){ kx++,ky=0; } else ky++; } return; } } } |
f) 深度优先搜索dfs
这里我用一维代替二维坐标，然后dfs的时候求出对应的位置。
然后就是简单带回溯的搜索了。
|
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
|
void dfs(int id){ int x = id/7; int y = id%7; if(x<2 && y==6){ dfs(id+1); } if(x==6 && y==3){ // printf("Success!\n"); for(int i=0;i<7;i++){ for(int j=0;j<7;j++){ if(mp[i][j]=='.') continue; putchar(mp[i][j]); } putchar('\n'); } exit(0); } if(mp[x][y]!='.') dfs(id+1); for(int i=1;i<=8;i++){ if(!vis[i]){ for(int j=1;j<=8;j++){ if(candown(x,y,i,j)){ down(x,y,i,j); vis[i] = 1; dfs(id+1); undown(x,y,i,j); vis[i] = 0; } } } }} |
2.完整程序
我这里找到解就退出，如果想要找到每个解的所有情况，可以自行修改代码。即对应dfs里的exit(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
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
|
#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull; const int N=1e3+5,M=2e8+5,inf=0x3f3f3f3f,mod=1e9+7;const int hashmod[8] = {802653189,805306857,1610612781,998288353};#define mst(a,b) memset(a,b,sizeof a)#define db double#define PII pair<int,int>#define PLL pair<ll,ll>#define x first#define y second#define pb emplace_back#define SZ(a) (int)a.size()#define rep(i,a,b) for(int i=a;i<=b;++i)#define per(i,a,b) for(int i=a;i>=b;--i)#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){ for(int i=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); }template <typename T> //x=max(x,y) x=min(x,y)void cmx(T &x,T y){ if(x<y) x=y;}template <typename T>void cmn(T &x,T y){ if(x>y) x=y;}char a[9][5][5]={ {{'.','.','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'1','1','1','1'}, {'1','.','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'2','2','2','.'}, {'2','2','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'3','3','.','.'}, {'.','3','3','3'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'4','.','.','.'}, {'4','4','4','.'}, {'.','.','4','.'}, {'.','.','.','.'}}, {{'5','5','5','.'}, {'5','.','.','.'}, {'5','.','.','.'}, {'.','.','.','.'}}, {{'6','6','6','6'}, {'.','6','.','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'7','7','7','.'}, {'7','7','7','.'}, {'.','.','.','.'}, {'.','.','.','.'}}, {{'8','8','8','.'}, {'8','.','8','.'}, {'.','.','.','.'}, {'.','.','.','.'}}};char b[9][9][5][5];void filp(char a[5][5]){ for(int i=0;i<4;i++) for(int j=0;j<2;j++){ swap(a[i][j],a[i][3-j]); } }void pr(char a[5][5]){ for(int i=0;i<4;i++) { for(int j=0;j<4;j++){ putchar(a[i][j]); } putchar('\n'); }}void rot(char a[5][5]){ char b[5][5]; for(int i=0;i<4;i++){ for(int j=0;j<4;j++) b[i][j] = a[3-j][i]; } for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j] = b[i][j];}char mp[8][8]={ ".......", ".......", ".......", ".......", ".......", ".......", ".......",};void cp(char a[5][5],char b[5][5]){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++) a[i][j] = b[i][j]; a[i][4]='\0'; }}int vis[9];bool candown(int x,int y,int i,int j){ int sx = -1, sy = -1; for(int xx=0;xx<4;xx++) for(int yy=0;yy<4;yy++){ if(b[i][j][xx][yy] != '.'){ sx = xx; sy = yy; int kx =sx,ky= sy; while(kx<4 && ky<4){ int nx = x + kx-sx; int ny = y + ky-sy; //如果要覆盖 if(b[i][j][kx][ky]!='.'){ if(nx<0 || ny<0) return false; if(nx<2 && ny<=5){ if(mp[nx][ny]!='.') return false; // mp[nx][ny] = b[i][j][kx][ky]; } else if(nx<=5 && nx>=2 && ny<=6){ if(mp[nx][ny]!='.') return false; // mp[nx][ny] = b[i][j][kx][ky]; } else if(nx==6 && ny<=2){ if(mp[nx][ny]!='.') return false; // mp[nx][ny] = b[i][j][kx][ky]; } else return false; } if(ky==3){ kx++,ky=0; } else ky++; } return true; } } return false;}void down(int x,int y,int i,int j){ for(int xx=0;xx<4;xx++) for(int yy=0;yy<4;yy++){ if(b[i][j][xx][yy] != '.'){ int kx =xx,ky= yy; while(kx<4 && ky<4){ int nx = x + kx-xx; int ny = y + ky-yy; if(b[i][j][kx][ky]!='.'){ mp[nx][ny] = b[i][j][kx][ky]; } if(ky==3){ kx++,ky=0; } else ky++; } return; } } }void undown(int x,int y,int i,int j){ for(int xx=0;xx<4;xx++) for(int yy=0;yy<4;yy++){ if(b[i][j][xx][yy] != '.'){ int kx =xx,ky= yy; while(kx<4 && ky<4){ int nx = x + kx-xx; int ny = y + ky-yy; if(b[i][j][kx][ky]!='.'){ mp[nx][ny] = '.'; } if(ky==3){ kx++,ky=0; } else ky++; } return; } } }void dfs(int id){ int x = id/7; int y = id%7; if(x<2 && y==6){ dfs(id+1); } if(x==6 && y==3){ // printf("Success!\n"); for(int i=0;i<7;i++){ for(int j=0;j<7;j++){ if(mp[i][j]=='.') continue; putchar(mp[i][j]); } putchar('\n'); } exit(0); } if(mp[x][y]!='.') dfs(id+1); for(int i=1;i<=8;i++){ if(!vis[i]){ for(int j=1;j<=8;j++){ if(candown(x,y,i,j)){ down(x,y,i,j); vis[i] = 1; dfs(id+1); undown(x,y,i,j); vis[i] = 0; } } } }}int main(){ int m,d; scanf("%d%d",&m,&d); //初始化 mp[m>6][(m-1)%6] = '0'; mp[((d-1)/7)+2][(d-1)%7] = '0'; //得到每个拼图的所有情况 for(int i=1;i<=8;i++){ cp(b[i][1],a[i]);filp(a[i]); cp(b[i][2],a[i]);filp(a[i]);rot(a[i]); cp(b[i][3],a[i]);filp(a[i]); cp(b[i][4],a[i]);filp(a[i]);rot(a[i]); cp(b[i][5],a[i]);filp(a[i]); cp(b[i][6],a[i]);filp(a[i]);rot(a[i]); cp(b[i][7],a[i]);filp(a[i]); cp(b[i][8],a[i]); } dfs(0); return 0;} |
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注服务器之家的更多内容!
原文链接：https://blog.csdn.net/weixin_45750972/article/details/123051047
