益智游戏日历拼图解法：搜索+回溯
这个是某夕夕上最近很火的一款益智小游戏，版面设计看起来也很nice！那么类似这种游戏对于程序员的正确打开方式还是写个程序解决，并没有什么益智不益智，因为说实话拼这个东西还是太费力了。
那么怎么解决这个问题呢？很明显先把盘子还有各个小块的形状记录起来，盘子用一个全局数组，而小块则用一个结构体node，还要存储长宽，并且有旋转等函数，然后采用深度优先搜索算法（DFS，这是一个很基础的算法，还没了解的应该先了解），注意回溯，然后就能罗列所有的情况，这个（右边的）差不多是7*7大小的，并且总共有8个小块，那么每个小块大概有7*7*8种放置的方式（加上旋转和翻转，一开始没想到翻转搞多了很多时间），因此计算量（粗略的说法，放置一块的意思，包括判断、更新数组等等操作）就最多是(7*7*8)^8次（大概五万亿亿次，粗略算1亿次1秒，但是加上很多不可能的情况（判断一下就过了）还有剪枝（去掉了极多的情况），还有这个是最大估计，其实远小于五万亿秒，本人跑了半个多小时，虽说还是不少）。再加上适当判断，排序，存文件等等，我们就能愉快的完成任务了！话不多说，代码如下：
#include<iostream>
#include<cstring>
#include<fstream>
#include<map>
#include<algorithm>
using namespace std;
const int ma[12] = { 31,29,31,30,31,30,31,31,30,31,30,31 };
int day_num = 0;
int pan[10][10];
struct node {
node()
{
memset(arr, 0, sizeof arr);
}
int n, m;
int c;
bool st[2][4];//哪几次旋转是没用的
bool arr[10][10];
void rotate()//有些可能转了等于没转，所以要四种状态都存起来
{
bool tmp[10][10];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
tmp[j][n - 1 - i] = arr[i][j];
}
}
memcpy(arr, tmp, sizeof arr);
swap(n, m);
}
void flip()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m / 2; j++)//要不然白换了
{
swap(arr[i][j], arr[i][m - 1 - j]);
}
}
}
void judge()
{
memset(st, 0, sizeof st);
bool tmp[8][10][10];
memset(tmp, 0, sizeof tmp);
int cnt = 0;
for (int t = 0; t < 2; t++)
{
for (int i = 0; i < 4; i++)
{
bool FLAG = 1;
for (int j = 0; j < cnt; j++)
{
bool flag = 0;
for (int ii = 0; ii < n; ii++)
{
for (int jj = 0; jj < m; jj++)
{
if (tmp[j][ii][jj] != arr[ii][jj])
{
flag = 1;
break;
}
}
if (flag)break;
}
if (!flag)//完全相同
{
FLAG = 0;
st[t][i] = 1;//第i次循环的状态跟前面重复了
}
}
if (FLAG)
{
for (int ii = 0; ii < n; ii++)
{
for (int jj = 0; jj < m; jj++)
{
tmp[cnt][ii][jj] = arr[ii][jj];
}
}
cnt++;
}
rotate();
}
flip();
}
}
void pt(int x, int y, bool f = 1)//从x,y开始
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int xx = x + i, yy = y + j;
if (arr[i][j])
{
if (f)pan[xx][yy] = c;
else pan[xx][yy] = 0;
}
}
}
}
}nd[8];
inline void printPan(ofstream &ofs, int pan[][10])
{
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
if (pan[i][j] != -1)ofs << pan[i][j] << " ";
else ofs << " ";
}
ofs << "\n";
}
ofs << "\n";
}
void prework()
{
for (int i = 0; i < 12; i++) day_num += ma[i];
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
pan[i][j] = 0;
}
}
pan[0][6] = pan[1][6] = pan[6][3] = pan[6][4] = pan[6][5] = pan[6][6] = -1;
for (int i = 0; i < 8; i++)nd[i].c = i + 1;
nd[0].n = 2, nd[0].m = 3;
for (int i = 0; i < 2; i++)for (int j = 0; j < 3; j++)nd[0].arr[i][j] = 1;
nd[1].n = 3, nd[1].m = 3;
for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)nd[1].arr[i][j] = 1;
for (int i = 1; i < 3; i++)for (int j = 0; j < 2; j++)nd[1].arr[i][j] = 0;
nd[2].n = 4, nd[2].m = 2;
for (int i = 0; i < 4; i++)for (int j = 0; j < 2; j++)nd[2].arr[i][j] = 1;
nd[2].arr[0][1] = nd[2].arr[2][1] = nd[2].arr[3][1] = 0;
nd[3].n = 3, nd[3].m = 2;
for (int i = 0; i < 3; i++)for (int j = 0; j < 2; j++)nd[3].arr[i][j] = 1;
nd[3].arr[1][0] = 0;
nd[4].n = 2, nd[4].m = 3;
for (int i = 0; i < 2; i++)for (int j = 0; j < 3; j++)nd[4].arr[i][j] = 1;
nd[4].arr[0][0] = 0;
nd[5].n = 4, nd[5].m = 2;
for (int i = 0; i < 4; i++)for (int j = 0; j < 2; j++)nd[5].arr[i][j] = 1;
nd[5].arr[0][0] = nd[5].arr[2][1] = nd[5].arr[3][1] = 0;
nd[6].n = 3, nd[6].m = 3;
for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)nd[6].arr[i][j] = 1;
nd[6].arr[0][0] = nd[6].arr[0][1] = nd[6].arr[2][1] = nd[6].arr[2][2] = 0;
nd[7].n = 2, nd[7].m = 4;
for (int j = 0; j < 4; j++)nd[7].arr[1][j] = 1;
nd[7].arr[0][3] = 1;
for (int i = 0; i < 8; i++)nd[i].judge();
}
inline bool check(int x, int y)
{
return x >= 0 && x < 7 && y >= 0 && y < 7 && pan[x][y] == 0;
}
struct date {
int m, d;
int arr[10][10];
bool operator<(const date &a)const
{
return m < a.m || m == a.m&&d < a.d;
}
}ans[400];
map<int, bool>mp;
int _cnt = 0;
ofstream ofs("答案.txt");
inline void printMpSize()
{
int cnt = 0;
for (map<int, bool>::iterator it = mp.begin(); it != mp.end(); it++)
{
if (it->second)cnt++;
}
cout << cnt << "\n";
}
void save()
{
printMpSize();
int id[2][2] = { -1 };
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
if (!pan[i][j])
{
if (id[0][0] == -1)
{
id[0][0] = i;
id[0][1] = j;
}
else
{
id[1][0] = i;
id[1][1] = j;
}
}
}
}
if ((id[0][0] - 1.5)*(id[1][0] - 1.5) > 0) return;//都不是或都是月份
int m, d;
if (id[0][0] < 2)m = id[0][0] * 6 + id[0][1], d = (id[1][0] - 2) * 7 + id[1][1];
else m = id[1][0] * 6 + id[1][1], d = (id[0][0] - 2) * 7 + id[0][1];
if (d >= ma[m])return;
if (mp[m * 100 + d])return;
mp[m * 100 + d] = 1;
ans[_cnt].m = m + 1;
ans[_cnt].d = d + 1;
memcpy(ans[_cnt].arr, pan, sizeof pan);
_cnt++;
}
void dfs(int x)//第x个
{
if (_cnt >= day_num)return;
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
for (int fl = 0; fl < 2; fl++)
{
for (int r = 0; r < 4; r++)//旋转
{
if (nd[x].st[fl][r])
{
nd[x].rotate();
continue;
}
bool flag = 0;
int n = nd[x].n, m = nd[x].m;
for (int ii = 0; ii < n; ii++)
{
for (int jj = 0; jj < m; jj++)
{
int xx = i + ii, yy = j + jj;
if (nd[x].arr[ii][jj] && !check(xx, yy))
{
flag = 1;
break;
}
}
if (flag)break;
}
if (!flag)//flag为0，可以装，装完继续搜
{
nd[x].pt(i, j);
if (x == 7)
{
save();
}
else
{
dfs(x + 1);
}
nd[x].pt(i, j, 0);
}
nd[x].rotate();
}
nd[x].flip();
}
}
}
}
int main()
{
prework();
dfs(0);
sort(ans, ans + _cnt);
for (int i = 0; i < _cnt; i++)
{
date &a = ans[i];
ofs << a.m << "月" << a.d << "日" << "\n";
printPan(ofs, a.arr);
}
ofs.close();
return 0;
}至于这个游戏的合理性证明我也是想不通，真是非常其妙，结果真的跑出每个日期的拼法。下面展示两个日期：
8月19日
4 4 1 1 1 2
4 0 1 1 1 2
4 4 7 2 2 2 3
7 7 7 6 6 6 3
7 5 6 6 0 3 3
5 5 8 8 8 8 3
5 5 8
10月1日
1 1 1 2 2 2
1 1 1 0 6 2
0 4 4 4 6 2 8
3 4 7 4 6 6 8
3 3 7 7 7 6 8
3 5 5 5 7 8 8
3 5 5
另外，对于完全不懂编程或者不懂算法或者不想花半个小时运行程序的话，这里提供了直接下载答案的地址：答案。点集红色箭头直指向的地方就能下载，下载后的那些问号是日和月，并不会乱码。
