C++日歷拼圖的解法你了解嗎
更新時間：2022年02月22日 10:11:13 作者：Harris-H
這篇文章主要為大家詳細(xì)介紹了日歷拼圖C++的解法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
日歷拼圖C++解法
0.介紹
任何一個日期都可以用8塊拼圖拼起來。
如12月3日：
1.思路
主要的思想就是深度優(yōu)先搜索。
a) 用字符串?dāng)?shù)組存8種拼圖塊
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種放置方式
這里我使用旋轉(zhuǎn)加翻轉(zhuǎn)實現(xiàn)的。
[2] 最開始為第一個，然后翻轉(zhuǎn)得到第二個。
[3] 再翻轉(zhuǎn)回來，再順時針90度得到第三個。
重復(fù)[2] [3] 步驟就可以得到8種放置方式。
翻轉(zhuǎn)代碼
也就是左右交換。
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]);
}
}
旋轉(zhuǎn)代碼
這里我是順時針旋轉(zhuǎn)90度。
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) 判斷某一個位置是否可以放置對應(yīng)的拼圖塊。
這里我們以左上角第一個非.的位置為起點，然后進(jìn)行判斷。
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 步類似。
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 步類似。
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) 深度優(yōu)先搜索dfs
這里我用一維代替二維坐標(biāo)，然后dfs的時候求出對應(yīng)的位置。
然后就是簡單帶回溯的搜索了。
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.完整程序
我這里找到解就退出，如果想要找到每個解的所有情況，可以自行修改代碼。即對應(yīng)dfs里的exit(0) 去掉。
#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;
}
總結(jié)
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
這篇文章主要介紹了C/C++中虛基類的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
C語言中結(jié)構(gòu)體、聯(lián)合體的成員內(nèi)存對齊情況
這篇文章主要給大家介紹了關(guān)于C語言中結(jié)構(gòu)體、聯(lián)合體的成員內(nèi)存對齊情況的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
快速排序是比較快的排序方法。它的基本思想是通過一組排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，本文將用C++實現(xiàn)快速排序算法，需要的可以參考一下2022-09-09
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)小學(xué)生隨機出題測試計分，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
本篇文章是對打印菱形及斐波納契數(shù)列的幾種解法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
這篇文章主要介紹了C語言實現(xiàn)abs和fabs絕對值，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
這篇文章主要為大家詳細(xì)介紹了C++基礎(chǔ)知識之運算符重載，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
對C++了解的人都應(yīng)該知道虛函數(shù)（Virtual Function）是通過一張?zhí)摵瘮?shù)表（Virtual Table）來實現(xiàn)的。簡稱為V-Table。本文就將詳細(xì)講講虛函數(shù)表的原理與使用，需要的可以參考一下2022-08-08
關(guān)于C++復(fù)制構(gòu)造函數(shù)的實現(xiàn)講解
今天小編就為大家分享一篇關(guān)于關(guān)于C++復(fù)制構(gòu)造函數(shù)的實現(xiàn)講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
C++ 標(biāo)準(zhǔn)模板庫 STL（Standard Template Library） 一共給我們提供了四種智能指針：auto_ptr、unique_ptr、shared_ptr 和 weak_ptr，今天給大家詳細(xì)介紹這幾種指針的具體用法，需要的朋友參考下吧2021-06-06