C++日歷拼圖的解法你了解嗎
日歷拼圖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)實(shí)現(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)的拼圖塊。
這里我們以左上角第一個非.
的位置為起點(diǎn),然后進(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語言中結(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超詳細(xì)解析C++實(shí)現(xiàn)快速排序算法的方法
快速排序是比較快的排序方法。它的基本思想是通過一組排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,本文將用C++實(shí)現(xiàn)快速排序算法,需要的可以參考一下2022-09-09C語言實(shí)現(xiàn)小學(xué)生隨機(jī)出題測試計(jì)分
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)小學(xué)生隨機(jī)出題測試計(jì)分,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-03-03關(guān)于C++復(fù)制構(gòu)造函數(shù)的實(shí)現(xiàn)講解
今天小編就為大家分享一篇關(guān)于關(guān)于C++復(fù)制構(gòu)造函數(shù)的實(shí)現(xiàn)講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2018-12-12