日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C++日歷拼圖的解法你了解嗎_C 語言

作者：Harris-H ? 更新時間： 2022-04-26 編程語言

日歷拼圖C++解法

0.介紹

任何一個日期都可以用8塊拼圖拼起來。

在這里插入圖片描述

如12月3日：

在這里插入圖片描述

1.思路

主要的思想就是深度優先搜索。

a) 用字符串數組存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種放置方式

這里我使用旋轉加翻轉實現的。

[2] 最開始為第一個，然后翻轉得到第二個。

[3] 再翻轉回來，再順時針90度得到第三個。

重復[2] [3] 步驟就可以得到8種放置方式。

翻轉代碼

也就是左右交換。

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度。

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) 判斷某一個位置是否可以放置對應的拼圖塊。

這里我們以左上角第一個非.的位置為起點，然后進行判斷。

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) 深度優先搜索dfs

這里我用一維代替二維坐標，然后dfs的時候求出對應的位置。

然后就是簡單帶回溯的搜索了。

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) 去掉。

#include
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
#define PLL pair
#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		//x=max(x,y)  x=min(x,y)
void cmx(T &x,T y){
	if(x
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

欄目分類
最近更新