Yurchiu
An AFO whker.

  首页

  归档

158

  标签

81

  分类

24

  说说

  关于

  留言

  链接

  设置

P4205 [NOI2005] 智慧珠游戏

Yurchiu 2020-02-17, 17:52:48 9k 隐藏左右两栏 展示左右两栏

首页 / P4205 [NOI2005] 智慧珠游戏

分享到

题解 P4205 [NOI2005] 智慧珠游戏

思路

由于 code 过于庞大，先不放。

小时候，你玩智障慧珠；长大后，智障慧珠玩你。

这是我的第一道黑题！！！是不是很弱~

本题解使用 dfs 做法。

约定

文中出现的词语定义

• 零件：指题目中 $\lceil$ $12$ 个形态各异的零件 $\rfloor$ 中的零件。
• 零件形态：指一个零件能通过旋转和翻转所能形成的图案。
• 珠子：指零件中的珠子。

变量

int num[]={0,4,2,8,1,4,8,4,8,8,1,4,8};
//各零件形态数
char a[10+5][10+5];
//存图案
bool v[20];
//零件是否使用过
int tal=0;
//阈值，意义后文有

宏

#define a(q,w,e) if(a[px+q][py+w]!='.')return 0/*指这个地方有零件放入*/;
//检验这个零件是否能放下(参数e是用不到的，无影响)
#define a(q,w,e) a[px+q][py+w]=e
//打标记
#define a(q,w,e) a[px+q][py+w]='.'
//回溯(参数e是用不到的，无影响)

//与后面的“函数”一一对应

函数

//3个宏+打表部分(见后文)=3个函数：
bool check(int type,int round,int px,int py)//最后要 return 1，即既然前面没有 return 0，则这个位置是合法的
//检验这个零件是否能放下
void seter(int type,int round,int px,int py)
//打标记
void clean(int type,int round,int px,int py)
//回溯

参数意义：

• type 零件；
• round 零件形态；
• px,py 坐标。

打表

先手动打表，把所有零件的零件形态记录下来。

零件有 $12$ 种，且所有的零件都允许旋转和翻转，所以需打表 $60$ 种情况：

零件	A	B	C	D	E	F	G	H	I	J	K	L	合计
零件形态总数	4	2	8	1	4	8	4	8	8	1	4	8	60

打表各零件中各珠子的相对坐标。以下是打表代码：

	switch(type)
	{
		case 1:
			switch(round)
			{
				case 1:a(0,0,'A'),a(0,1,'A'),a(1,0,'A');break;
				case 2:a(1,1,'A'),a(0,1,'A'),a(0,0,'A');break;
				case 3:a(1,0,'A'),a(0,0,'A'),a(1,-1,'A');break;
				case 4:a(1,1,'A'),a(0,0,'A'),a(1,0,'A');break;
			}break;
		case 2:
			switch(round)
			{
				case 1:a(0,0,'B'),a(0,1,'B'),a(0,2,'B'),a(0,3,'B');break;
				case 2:a(0,0,'B'),a(1,0,'B'),a(2,0,'B'),a(3,0,'B');break;
			}break;
		case 3:
			switch(round)
			{
				case 1:a(0,0,'C'),a(0,1,'C'),a(1,0,'C'),a(0,2,'C');break;
				case 2:a(0,0,'C'),a(1,0,'C'),a(2,0,'C'),a(2,1,'C');break;
				case 3:a(0,0,'C'),a(1,0,'C'),a(1,-1,'C'),a(1,-2,'C');break;
				case 4:a(0,0,'C'),a(0,1,'C'),a(1,1,'C'),a(2,1,'C');break;
				case 5:a(0,0,'C'),a(1,0,'C'),a(1,1,'C'),a(1,2,'C');break;
				case 6:a(0,0,'C'),a(0,1,'C'),a(1,0,'C'),a(2,0,'C');break;
				case 7:a(0,0,'C'),a(0,1,'C'),a(0,2,'C'),a(1,2,'C');break;
				case 8:a(0,0,'C'),a(1,0,'C'),a(2,0,'C'),a(2,-1,'C');break;
			}break;
		case 4:
			switch(round)
			{
				case 1:a(0,0,'D'),a(0,1,'D'),a(1,0,'D'),a(1,1,'D');break;
			}break;
		case 5:
			switch(round)
			{
				case 1:a(0,0,'E'),a(0,1,'E'),a(0,2,'E'),a(1,0,'E'),a(2,0,'E');break;
				case 2:a(0,0,'E'),a(1,0,'E'),a(2,0,'E'),a(2,-1,'E'),a(2,-2,'E');break;
				case 3:a(0,0,'E'),a(0,1,'E'),a(0,2,'E'),a(1,2,'E'),a(2,2,'E');break;
				case 4:a(0,0,'E'),a(2,1,'E'),a(2,2,'E'),a(1,0,'E'),a(2,0,'E');break;
			}break;
		case 6:
			switch(round)
			{
				case 1:a(0,0,'F'),a(0,1,'F'),a(0,2,'F'),a(0,3,'F'),a(1,1,'F');break;
				case 2:a(0,0,'F'),a(0,1,'F'),a(0,2,'F'),a(0,3,'F'),a(1,2,'F');break;
				case 3:a(1,-1,'F'),a(1,0,'F'),a(1,1,'F'),a(1,2,'F'),a(0,0,'F');break;
				case 4:a(0,0,'F'),a(1,0,'F'),a(1,1,'F'),a(1,-1,'F'),a(1,-2,'F');break;
				case 5:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(1,1,'F');break;
				case 6:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(2,1,'F');break;
				case 7:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(1,-1,'F');break;
				case 8:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(2,-1,'F');break;
			}break;
		case 7:
			switch(round)
			{
				case 1:a(0,0,'G'),a(0,1,'G'),a(0,2,'G'),a(1,0,'G'),a(1,2,'G');break;
				case 2:a(1,0,'G'),a(1,1,'G'),a(1,2,'G'),a(0,0,'G'),a(0,2,'G');break;
				case 3:a(0,1,'G'),a(1,1,'G'),a(2,1,'G'),a(0,0,'G'),a(2,0,'G');break;
				case 4:a(0,0,'G'),a(1,0,'G'),a(2,0,'G'),a(0,1,'G'),a(2,1,'G');break;
			}break;
		case 8:
			switch(round)
			{
				case 1:a(0,0,'H'),a(0,1,'H'),a(0,2,'H'),a(1,0,'H'),a(1,1,'H');break;
				case 2:a(0,0,'H'),a(0,1,'H'),a(0,2,'H'),a(1,1,'H'),a(1,2,'H');break;
				case 3:a(0,0,'H'),a(0,1,'H'),a(1,0,'H'),a(1,1,'H'),a(1,-1,'H');break;
				case 4:a(1,0,'H'),a(1,1,'H'),a(0,0,'H'),a(2,1,'H'),a(0,1,'H');break;
				case 5:a(0,0,'H'),a(1,0,'H'),a(2,0,'H'),a(2,1,'H'),a(1,1,'H');break;
				case 6:a(0,0,'H'),a(1,-1,'H'),a(2,-1,'H'),a(1,0,'H'),a(2,0,'H');break;
				case 7:a(0,1,'H'),a(1,1,'H'),a(1,2,'H'),a(0,0,'H'),a(1,0,'H');break;
				case 8:a(0,1,'H'),a(1,1,'H'),a(2,0,'H'),a(0,0,'H'),a(1,0,'H');break;
			}break;
		case 9:
			switch(round)
			{
				case 1:a(0,0,'I'),a(0,1,'I'),a(0,2,'I'),a(1,2,'I'),a(1,3,'I');break;
				case 2:a(1,-1,'I'),a(0,0,'I'),a(1,0,'I'),a(2,-1,'I'),a(3,-1,'I');break;
				case 3:a(0,0,'I'),a(1,1,'I'),a(1,2,'I'),a(1,3,'I'),a(0,1,'I');break;
				case 4:a(0,0,'I'),a(0,1,'I'),a(1,0,'I'),a(1,-1,'I'),a(1,-2,'I');break;
				case 5:a(0,0,'I'),a(1,0,'I'),a(2,0,'I'),a(2,-1,'I'),a(3,-1,'I');break;
				case 6:a(0,0,'I'),a(1,0,'I'),a(2,0,'I'),a(2,1,'I'),a(3,1,'I');break;
				case 7:a(0,0,'I'),a(0,1,'I'),a(0,2,'I'),a(1,0,'I'),a(1,-1,'I');break;
				case 8:a(0,0,'I'),a(1,0,'I'),a(1,1,'I'),a(2,1,'I'),a(3,1,'I');break;
			}break;
		case 10:
			switch(round)
			{
				case 1:a(0,0,'J'),a(1,0,'J'),a(2,0,'J'),a(1,-1,'J'),a(1,1,'J');break;
			}break;
		case 11:
			switch(round)
			{
				case 1:a(0,0,'K'),a(1,0,'K'),a(1,1,'K'),a(2,1,'K'),a(2,2,'K');break;
				case 2:a(0,0,'K'),a(1,0,'K'),a(1,-1,'K'),a(2,-1,'K'),a(2,-2,'K');break;
				case 3:a(0,0,'K'),a(1,0,'K'),a(1,-1,'K'),a(2,-1,'K'),a(0,1,'K');break;
				case 4:a(0,0,'K'),a(0,1,'K'),a(1,1,'K'),a(1,2,'K'),a(2,2,'K');break;
			}break;
		case 12:
			switch(round)
			{
				case 1:a(0,0,'L'),a(0,1,'L'),a(0,2,'L'),a(0,3,'L'),a(1,0,'L');break;
				case 2:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(3,1,'L');break;
				case 3:a(0,0,'L'),a(1,0,'L'),a(1,-1,'L'),a(1,-2,'L'),a(1,-3,'L');break;
				case 4:a(0,0,'L'),a(0,1,'L'),a(1,1,'L'),a(2,1,'L'),a(3,1,'L');break;
				case 5:a(1,0,'L'),a(1,1,'L'),a(1,2,'L'),a(1,3,'L'),a(0,0,'L');break;
				case 6:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(0,1,'L');break;
				case 7:a(0,1,'L'),a(0,0,'L'),a(1,3,'L'),a(0,2,'L'),a(0,3,'L');break;
				case 8:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(3,-1,'L');break;
			}break;
	}

打表两点注意事项（我踩过的坑）：

• 打表部分中必须有坐标为 $(0,0)$ 的点。

• 确保零件的放置不会对前面已放上的零件造成影响——打表部分中坐标为 $(0,0)$ 的点的左面与上面没有点。

  例如以下（形状都为:.形）：

  • 合法：$(0,0)$，$(1,0)$，$(1,1)$。
  • 不合法：$(0,0)$，$(-1,0)$，$(0,1)$。

暴力 dfs

void dfs(int step)
{
    //********************解的判断
	bool flag=1;
	for(int i=1;i<=12;i++)
		if(v[i]==0)
			flag=0;
	if(flag)//零件都用了
	{
		for(int i=1;i<=10;i++)
		{
			for(int j=1;j<=i;j++)
				cout<<a[i][j];
			cout<<endl;
		}
		exit(0);//输出并立刻结束程序
	}
    //********************递归数阈值
	tal++;
	if(tal>2500000)//马上要TLE了，赶紧结束程序。这个地方别的题解有所提及
		printf("No solution"),exit(0);
    //********************从上至下寻找还未填的地方
	int x,y;
	for(x=1;x<=10;x++)
		for(y=1;y<=x;y++)
			if(a[x][y]=='.')
				goto end;//用break麻烦
	end:
    //********************枚举算符（若打表部分没满足前文的两点要求，会WA）
	for(int i=1;i<=12;i++)//枚举各零件
		if(v[i]==0)
		{
			v[i]=1;
			for(int j=1;j<=num[i];j++)//枚举各零件的各零件形态
				if(check(i,j,x,y))//三个函数意义前文已有解释
				{
					seter(i,j,x,y);
					dfs(step+1);
					clean(i,j,x,y);
				}
			v[i]=0;
		}
}

纯暴力 $+$ 防 TLE 剪枝 $=$ AC 。

注：dfs 好像无需参数。

CODE

为了方便你复制，以下是 code 全貌：

#include<bits/stdc++.h>
using namespace std;
char a[10+5][10+5];
int v[200],num[20]={0,4,2,8,1,4,8,4,8,8,1,4,8},tal=0;
//前方高能！！！其实三个函数完全可以合并。
//只是懒得写。
bool check(int type,int round,int px,int py)
{
	#define a(q,w,e) if(a[px+q][py+w]!='.')return 0;
	switch(type)
	{
		case 1:
			switch(round)
			{
				case 1:a(0,0,'A') a(0,1,'A') a(1,0,'A');break;
				case 2:a(1,1,'A') a(0,1,'A') a(0,0,'A');break;
				case 3:a(1,0,'A') a(0,0,'A') a(1,-1,'A');break;
				case 4:a(1,1,'A') a(0,0,'A') a(1,0,'A');break;
			}break;
		case 2:
			switch(round)
			{
				case 1:a(0,0,'B') a(0,1,'B') a(0,2,'B') a(0,3,'B');break;
				case 2:a(0,0,'B') a(1,0,'B') a(2,0,'B') a(3,0,'B');break;
			}break;
		case 3:
			switch(round)
			{
				case 1:a(0,0,'C') a(0,1,'C') a(1,0,'C') a(0,2,'C');break;
				case 2:a(0,0,'C') a(1,0,'C') a(2,0,'C') a(2,1,'C');break;
				case 3:a(0,0,'C') a(1,0,'C') a(1,-1,'C') a(1,-2,'C');break;
				case 4:a(0,0,'C') a(0,1,'C') a(1,1,'C') a(2,1,'C');break;
				case 5:a(0,0,'C') a(1,0,'C') a(1,1,'C') a(1,2,'C');break;
				case 6:a(0,0,'C') a(0,1,'C') a(1,0,'C') a(2,0,'C');break;
				case 7:a(0,0,'C') a(0,1,'C') a(0,2,'C') a(1,2,'C');break;
				case 8:a(0,0,'C') a(1,0,'C') a(2,0,'C') a(2,-1,'C');break;
			}break;
		case 4:
			switch(round)
			{
				case 1:a(0,0,'D') a(0,1,'D') a(1,0,'D') a(1,1,'D');break;
			}break;
		case 5:
			switch(round)
			{
				case 1:a(0,0,'E') a(0,1,'E') a(0,2,'E') a(1,0,'E') a(2,0,'E');break;
				case 2:a(0,0,'E') a(1,0,'E') a(2,0,'E') a(2,-1,'E') a(2,-2,'E');break;
				case 3:a(0,0,'E') a(0,1,'E') a(0,2,'E') a(1,2,'E') a(2,2,'E');break;
				case 4:a(0,0,'E') a(2,1,'E') a(2,2,'E') a(1,0,'E') a(2,0,'E');break;
			}break;
		case 6:
			switch(round)
			{
				case 1:a(0,0,'F') a(0,1,'F') a(0,2,'F') a(0,3,'F') a(1,1,'F');break;
				case 2:a(0,0,'F') a(0,1,'F') a(0,2,'F') a(0,3,'F') a(1,2,'F');break;
				case 3:a(1,-1,'F') a(1,0,'F') a(1,1,'F') a(1,2,'F') a(0,0,'F');break;
				case 4:a(0,0,'F') a(1,0,'F') a(1,1,'F') a(1,-1,'F') a(1,-2,'F');break;
				case 5:a(0,0,'F') a(1,0,'F') a(2,0,'F') a(3,0,'F') a(1,1,'F');break;
				case 6:a(0,0,'F') a(1,0,'F') a(2,0,'F') a(3,0,'F') a(2,1,'F');break;
				case 7:a(0,0,'F') a(1,0,'F') a(2,0,'F') a(3,0,'F') a(1,-1,'F');break;
				case 8:a(0,0,'F') a(1,0,'F') a(2,0,'F') a(3,0,'F') a(2,-1,'F');break;
			}break;
		case 7:
			switch(round)
			{
				case 1:a(0,0,'G') a(0,1,'G') a(0,2,'G') a(1,0,'G') a(1,2,'G');break;
				case 2:a(1,0,'G') a(1,1,'G') a(1,2,'G') a(0,0,'G') a(0,2,'G');break;
				case 3:a(0,1,'G') a(1,1,'G') a(2,1,'G') a(0,0,'G') a(2,0,'G');break;
				case 4:a(0,0,'G') a(1,0,'G') a(2,0,'G') a(0,1,'G') a(2,1,'G');break;
			}break;
		case 8:
			switch(round)
			{
				case 1:a(0,0,'H') a(0,1,'H') a(0,2,'H') a(1,0,'H') a(1,1,'H');break;
				case 2:a(0,0,'H') a(0,1,'H') a(0,2,'H') a(1,1,'H') a(1,2,'H');break;
				case 3:a(0,0,'H') a(0,1,'H') a(1,0,'H') a(1,1,'H') a(1,-1,'H');break;
				case 4:a(1,0,'H') a(1,1,'H') a(0,0,'H') a(2,1,'H') a(0,1,'H');break;
				case 5:a(0,0,'H') a(1,0,'H') a(2,0,'H') a(2,1,'H') a(1,1,'H');break;
				case 6:a(0,0,'H') a(1,-1,'H') a(2,-1,'H') a(1,0,'H') a(2,0,'H');break;
				case 7:a(0,1,'H') a(1,1,'H') a(1,2,'H') a(0,0,'H') a(1,0,'H');break;
				case 8:a(0,1,'H') a(1,1,'H') a(2,0,'H') a(0,0,'H') a(1,0,'H');break;
			}break;
		case 9:
			switch(round)
			{
				case 1:a(0,0,'I') a(0,1,'I') a(0,2,'I') a(1,2,'I') a(1,3,'I');break;
				case 2:a(1,-1,'I') a(0,0,'I') a(1,0,'I') a(2,-1,'I') a(3,-1,'I');break;
				case 3:a(0,0,'I') a(1,1,'I') a(1,2,'I') a(1,3,'I') a(0,1,'I');break;
				case 4:a(0,0,'I') a(0,1,'I') a(1,0,'I') a(1,-1,'I') a(1,-2,'I');break;
				case 5:a(0,0,'I') a(1,0,'I') a(2,0,'I') a(2,-1,'I') a(3,-1,'I');break;
				case 6:a(0,0,'I') a(1,0,'I') a(2,0,'I') a(2,1,'I') a(3,1,'I');break;
				case 7:a(0,0,'I') a(0,1,'I') a(0,2,'I') a(1,0,'I') a(1,-1,'I');break;
				case 8:a(0,0,'I') a(1,0,'I') a(1,1,'I') a(2,1,'I') a(3,1,'I');break;
			}break;
		case 10:
			switch(round)
			{
				case 1:a(0,0,'J') a(1,0,'J') a(2,0,'J') a(1,-1,'J') a(1,1,'J');break;
			}break;
		case 11:
			switch(round)
			{
				case 1:a(0,0,'K') a(1,0,'K') a(1,1,'K') a(2,1,'K') a(2,2,'K');break;
				case 2:a(0,0,'K') a(1,0,'K') a(1,-1,'K') a(2,-1,'K') a(2,-2,'K');break;
				case 3:a(0,0,'K') a(1,0,'K') a(1,-1,'K') a(2,-1,'K') a(0,1,'K');break;
				case 4:a(0,0,'K') a(0,1,'K') a(1,1,'K') a(1,2,'K') a(2,2,'K');break;
			}break;
		case 12:
			switch(round)
			{
				case 1:a(0,0,'L') a(0,1,'L') a(0,2,'L') a(0,3,'L') a(1,0,'L');break;
				case 2:a(0,0,'L') a(1,0,'L') a(2,0,'L') a(3,0,'L') a(3,1,'L');break;
				case 3:a(0,0,'L') a(1,0,'L') a(1,-1,'L') a(1,-2,'L') a(1,-3,'L');break;
				case 4:a(0,0,'L') a(0,1,'L') a(1,1,'L') a(2,1,'L') a(3,1,'L');break;
				case 5:a(1,0,'L') a(1,1,'L') a(1,2,'L') a(1,3,'L') a(0,0,'L');break;
				case 6:a(0,0,'L') a(1,0,'L') a(2,0,'L') a(3,0,'L') a(0,1,'L');break;
				case 7:a(0,1,'L') a(0,0,'L') a(1,3,'L') a(0,2,'L') a(0,3,'L');break;
				case 8:a(0,0,'L') a(1,0,'L') a(2,0,'L') a(3,0,'L') a(3,-1,'L');break;
			}break;
	}
	return 1;
}
void seter(int type,int round,int px,int py)
{
	#define a(q,w,e) a[px+q][py+w]=e
	switch(type)
	{
		case 1:
			switch(round)
			{
				case 1:a(0,0,'A'),a(0,1,'A'),a(1,0,'A');break;
				case 2:a(1,1,'A'),a(0,1,'A'),a(0,0,'A');break;
				case 3:a(1,0,'A'),a(0,0,'A'),a(1,-1,'A');break;
				case 4:a(1,1,'A'),a(0,0,'A'),a(1,0,'A');break;
			}break;
		case 2:
			switch(round)
			{
				case 1:a(0,0,'B'),a(0,1,'B'),a(0,2,'B'),a(0,3,'B');break;
				case 2:a(0,0,'B'),a(1,0,'B'),a(2,0,'B'),a(3,0,'B');break;
			}break;
		case 3:
			switch(round)
			{
				case 1:a(0,0,'C'),a(0,1,'C'),a(1,0,'C'),a(0,2,'C');break;
				case 2:a(0,0,'C'),a(1,0,'C'),a(2,0,'C'),a(2,1,'C');break;
				case 3:a(0,0,'C'),a(1,0,'C'),a(1,-1,'C'),a(1,-2,'C');break;
				case 4:a(0,0,'C'),a(0,1,'C'),a(1,1,'C'),a(2,1,'C');break;
				case 5:a(0,0,'C'),a(1,0,'C'),a(1,1,'C'),a(1,2,'C');break;
				case 6:a(0,0,'C'),a(0,1,'C'),a(1,0,'C'),a(2,0,'C');break;
				case 7:a(0,0,'C'),a(0,1,'C'),a(0,2,'C'),a(1,2,'C');break;
				case 8:a(0,0,'C'),a(1,0,'C'),a(2,0,'C'),a(2,-1,'C');break;
			}break;
		case 4:
			switch(round)
			{
				case 1:a(0,0,'D'),a(0,1,'D'),a(1,0,'D'),a(1,1,'D');break;
			}break;
		case 5:
			switch(round)
			{
				case 1:a(0,0,'E'),a(0,1,'E'),a(0,2,'E'),a(1,0,'E'),a(2,0,'E');break;
				case 2:a(0,0,'E'),a(1,0,'E'),a(2,0,'E'),a(2,-1,'E'),a(2,-2,'E');break;
				case 3:a(0,0,'E'),a(0,1,'E'),a(0,2,'E'),a(1,2,'E'),a(2,2,'E');break;
				case 4:a(0,0,'E'),a(2,1,'E'),a(2,2,'E'),a(1,0,'E'),a(2,0,'E');break;
			}break;
		case 6:
			switch(round)
			{
				case 1:a(0,0,'F'),a(0,1,'F'),a(0,2,'F'),a(0,3,'F'),a(1,1,'F');break;
				case 2:a(0,0,'F'),a(0,1,'F'),a(0,2,'F'),a(0,3,'F'),a(1,2,'F');break;
				case 3:a(1,-1,'F'),a(1,0,'F'),a(1,1,'F'),a(1,2,'F'),a(0,0,'F');break;
				case 4:a(0,0,'F'),a(1,0,'F'),a(1,1,'F'),a(1,-1,'F'),a(1,-2,'F');break;
				case 5:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(1,1,'F');break;
				case 6:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(2,1,'F');break;
				case 7:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(1,-1,'F');break;
				case 8:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(2,-1,'F');break;
			}break;
		case 7:
			switch(round)
			{
				case 1:a(0,0,'G'),a(0,1,'G'),a(0,2,'G'),a(1,0,'G'),a(1,2,'G');break;
				case 2:a(1,0,'G'),a(1,1,'G'),a(1,2,'G'),a(0,0,'G'),a(0,2,'G');break;
				case 3:a(0,1,'G'),a(1,1,'G'),a(2,1,'G'),a(0,0,'G'),a(2,0,'G');break;
				case 4:a(0,0,'G'),a(1,0,'G'),a(2,0,'G'),a(0,1,'G'),a(2,1,'G');break;
			}break;
		case 8:
			switch(round)
			{
				case 1:a(0,0,'H'),a(0,1,'H'),a(0,2,'H'),a(1,0,'H'),a(1,1,'H');break;
				case 2:a(0,0,'H'),a(0,1,'H'),a(0,2,'H'),a(1,1,'H'),a(1,2,'H');break;
				case 3:a(0,0,'H'),a(0,1,'H'),a(1,0,'H'),a(1,1,'H'),a(1,-1,'H');break;
				case 4:a(1,0,'H'),a(1,1,'H'),a(0,0,'H'),a(2,1,'H'),a(0,1,'H');break;
				case 5:a(0,0,'H'),a(1,0,'H'),a(2,0,'H'),a(2,1,'H'),a(1,1,'H');break;
				case 6:a(0,0,'H'),a(1,-1,'H'),a(2,-1,'H'),a(1,0,'H'),a(2,0,'H');break;
				case 7:a(0,1,'H'),a(1,1,'H'),a(1,2,'H'),a(0,0,'H'),a(1,0,'H');break;
				case 8:a(0,1,'H'),a(1,1,'H'),a(2,0,'H'),a(0,0,'H'),a(1,0,'H');break;
			}break;
		case 9:
			switch(round)
			{
				case 1:a(0,0,'I'),a(0,1,'I'),a(0,2,'I'),a(1,2,'I'),a(1,3,'I');break;
				case 2:a(1,-1,'I'),a(0,0,'I'),a(1,0,'I'),a(2,-1,'I'),a(3,-1,'I');break;
				case 3:a(0,0,'I'),a(1,1,'I'),a(1,2,'I'),a(1,3,'I'),a(0,1,'I');break;
				case 4:a(0,0,'I'),a(0,1,'I'),a(1,0,'I'),a(1,-1,'I'),a(1,-2,'I');break;
				case 5:a(0,0,'I'),a(1,0,'I'),a(2,0,'I'),a(2,-1,'I'),a(3,-1,'I');break;
				case 6:a(0,0,'I'),a(1,0,'I'),a(2,0,'I'),a(2,1,'I'),a(3,1,'I');break;
				case 7:a(0,0,'I'),a(0,1,'I'),a(0,2,'I'),a(1,0,'I'),a(1,-1,'I');break;
				case 8:a(0,0,'I'),a(1,0,'I'),a(1,1,'I'),a(2,1,'I'),a(3,1,'I');break;
			}break;
		case 10:
			switch(round)
			{
				case 1:a(0,0,'J'),a(1,0,'J'),a(2,0,'J'),a(1,-1,'J'),a(1,1,'J');break;
			}break;
		case 11:
			switch(round)
			{
				case 1:a(0,0,'K'),a(1,0,'K'),a(1,1,'K'),a(2,1,'K'),a(2,2,'K');break;
				case 2:a(0,0,'K'),a(1,0,'K'),a(1,-1,'K'),a(2,-1,'K'),a(2,-2,'K');break;
				case 3:a(0,0,'K'),a(1,0,'K'),a(1,-1,'K'),a(2,-1,'K'),a(0,1,'K');break;
				case 4:a(0,0,'K'),a(0,1,'K'),a(1,1,'K'),a(1,2,'K'),a(2,2,'K');break;
			}break;
		case 12:
			switch(round)
			{
				case 1:a(0,0,'L'),a(0,1,'L'),a(0,2,'L'),a(0,3,'L'),a(1,0,'L');break;
				case 2:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(3,1,'L');break;
				case 3:a(0,0,'L'),a(1,0,'L'),a(1,-1,'L'),a(1,-2,'L'),a(1,-3,'L');break;
				case 4:a(0,0,'L'),a(0,1,'L'),a(1,1,'L'),a(2,1,'L'),a(3,1,'L');break;
				case 5:a(1,0,'L'),a(1,1,'L'),a(1,2,'L'),a(1,3,'L'),a(0,0,'L');break;
				case 6:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(0,1,'L');break;
				case 7:a(0,1,'L'),a(0,0,'L'),a(1,3,'L'),a(0,2,'L'),a(0,3,'L');break;
				case 8:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(3,-1,'L');break;
			}break;
	}
	return;
}
void clean(int type,int round,int px,int py)
{
	#define a(q,w,e) a[px+q][py+w]='.'
	switch(type)
	{
		case 1:
			switch(round)
			{
				case 1:a(0,0,'A'),a(0,1,'A'),a(1,0,'A');break;
				case 2:a(1,1,'A'),a(0,1,'A'),a(0,0,'A');break;
				case 3:a(1,0,'A'),a(0,0,'A'),a(1,-1,'A');break;
				case 4:a(1,1,'A'),a(0,0,'A'),a(1,0,'A');break;
			}break;
		case 2:
			switch(round)
			{
				case 1:a(0,0,'B'),a(0,1,'B'),a(0,2,'B'),a(0,3,'B');break;
				case 2:a(0,0,'B'),a(1,0,'B'),a(2,0,'B'),a(3,0,'B');break;
			}break;
		case 3:
			switch(round)
			{
				case 1:a(0,0,'C'),a(0,1,'C'),a(1,0,'C'),a(0,2,'C');break;
				case 2:a(0,0,'C'),a(1,0,'C'),a(2,0,'C'),a(2,1,'C');break;
				case 3:a(0,0,'C'),a(1,0,'C'),a(1,-1,'C'),a(1,-2,'C');break;
				case 4:a(0,0,'C'),a(0,1,'C'),a(1,1,'C'),a(2,1,'C');break;
				case 5:a(0,0,'C'),a(1,0,'C'),a(1,1,'C'),a(1,2,'C');break;
				case 6:a(0,0,'C'),a(0,1,'C'),a(1,0,'C'),a(2,0,'C');break;
				case 7:a(0,0,'C'),a(0,1,'C'),a(0,2,'C'),a(1,2,'C');break;
				case 8:a(0,0,'C'),a(1,0,'C'),a(2,0,'C'),a(2,-1,'C');break;
			}break;
		case 4:
			switch(round)
			{
				case 1:a(0,0,'D'),a(0,1,'D'),a(1,0,'D'),a(1,1,'D');break;
			}break;
		case 5:
			switch(round)
			{
				case 1:a(0,0,'E'),a(0,1,'E'),a(0,2,'E'),a(1,0,'E'),a(2,0,'E');break;
				case 2:a(0,0,'E'),a(1,0,'E'),a(2,0,'E'),a(2,-1,'E'),a(2,-2,'E');break;
				case 3:a(0,0,'E'),a(0,1,'E'),a(0,2,'E'),a(1,2,'E'),a(2,2,'E');break;
				case 4:a(0,0,'E'),a(2,1,'E'),a(2,2,'E'),a(1,0,'E'),a(2,0,'E');break;
			}break;
		case 6:
			switch(round)
			{
				case 1:a(0,0,'F'),a(0,1,'F'),a(0,2,'F'),a(0,3,'F'),a(1,1,'F');break;
				case 2:a(0,0,'F'),a(0,1,'F'),a(0,2,'F'),a(0,3,'F'),a(1,2,'F');break;
				case 3:a(1,-1,'F'),a(1,0,'F'),a(1,1,'F'),a(1,2,'F'),a(0,0,'F');break;
				case 4:a(0,0,'F'),a(1,0,'F'),a(1,1,'F'),a(1,-1,'F'),a(1,-2,'F');break;
				case 5:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(1,1,'F');break;
				case 6:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(2,1,'F');break;
				case 7:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(1,-1,'F');break;
				case 8:a(0,0,'F'),a(1,0,'F'),a(2,0,'F'),a(3,0,'F'),a(2,-1,'F');break;
			}break;
		case 7:
			switch(round)
			{
				case 1:a(0,0,'G'),a(0,1,'G'),a(0,2,'G'),a(1,0,'G'),a(1,2,'G');break;
				case 2:a(1,0,'G'),a(1,1,'G'),a(1,2,'G'),a(0,0,'G'),a(0,2,'G');break;
				case 3:a(0,1,'G'),a(1,1,'G'),a(2,1,'G'),a(0,0,'G'),a(2,0,'G');break;
				case 4:a(0,0,'G'),a(1,0,'G'),a(2,0,'G'),a(0,1,'G'),a(2,1,'G');break;
			}break;
		case 8:
			switch(round)
			{
				case 1:a(0,0,'H'),a(0,1,'H'),a(0,2,'H'),a(1,0,'H'),a(1,1,'H');break;
				case 2:a(0,0,'H'),a(0,1,'H'),a(0,2,'H'),a(1,1,'H'),a(1,2,'H');break;
				case 3:a(0,0,'H'),a(0,1,'H'),a(1,0,'H'),a(1,1,'H'),a(1,-1,'H');break;
				case 4:a(1,0,'H'),a(1,1,'H'),a(0,0,'H'),a(2,1,'H'),a(0,1,'H');break;
				case 5:a(0,0,'H'),a(1,0,'H'),a(2,0,'H'),a(2,1,'H'),a(1,1,'H');break;
				case 6:a(0,0,'H'),a(1,-1,'H'),a(2,-1,'H'),a(1,0,'H'),a(2,0,'H');break;
				case 7:a(0,1,'H'),a(1,1,'H'),a(1,2,'H'),a(0,0,'H'),a(1,0,'H');break;
				case 8:a(0,1,'H'),a(1,1,'H'),a(2,0,'H'),a(0,0,'H'),a(1,0,'H');break;
			}break;
		case 9:
			switch(round)
			{
				case 1:a(0,0,'I'),a(0,1,'I'),a(0,2,'I'),a(1,2,'I'),a(1,3,'I');break;
				case 2:a(1,-1,'I'),a(0,0,'I'),a(1,0,'I'),a(2,-1,'I'),a(3,-1,'I');break;
				case 3:a(0,0,'I'),a(1,1,'I'),a(1,2,'I'),a(1,3,'I'),a(0,1,'I');break;
				case 4:a(0,0,'I'),a(0,1,'I'),a(1,0,'I'),a(1,-1,'I'),a(1,-2,'I');break;
				case 5:a(0,0,'I'),a(1,0,'I'),a(2,0,'I'),a(2,-1,'I'),a(3,-1,'I');break;
				case 6:a(0,0,'I'),a(1,0,'I'),a(2,0,'I'),a(2,1,'I'),a(3,1,'I');break;
				case 7:a(0,0,'I'),a(0,1,'I'),a(0,2,'I'),a(1,0,'I'),a(1,-1,'I');break;
				case 8:a(0,0,'I'),a(1,0,'I'),a(1,1,'I'),a(2,1,'I'),a(3,1,'I');break;
			}break;
		case 10:
			switch(round)
			{
				case 1:a(0,0,'J'),a(1,0,'J'),a(2,0,'J'),a(1,-1,'J'),a(1,1,'J');break;
			}break;
		case 11:
			switch(round)
			{
				case 1:a(0,0,'K'),a(1,0,'K'),a(1,1,'K'),a(2,1,'K'),a(2,2,'K');break;
				case 2:a(0,0,'K'),a(1,0,'K'),a(1,-1,'K'),a(2,-1,'K'),a(2,-2,'K');break;
				case 3:a(0,0,'K'),a(1,0,'K'),a(1,-1,'K'),a(2,-1,'K'),a(0,1,'K');break;
				case 4:a(0,0,'K'),a(0,1,'K'),a(1,1,'K'),a(1,2,'K'),a(2,2,'K');break;
			}break;
		case 12:
			switch(round)
			{
				case 1:a(0,0,'L'),a(0,1,'L'),a(0,2,'L'),a(0,3,'L'),a(1,0,'L');break;
				case 2:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(3,1,'L');break;
				case 3:a(0,0,'L'),a(1,0,'L'),a(1,-1,'L'),a(1,-2,'L'),a(1,-3,'L');break;
				case 4:a(0,0,'L'),a(0,1,'L'),a(1,1,'L'),a(2,1,'L'),a(3,1,'L');break;
				case 5:a(1,0,'L'),a(1,1,'L'),a(1,2,'L'),a(1,3,'L'),a(0,0,'L');break;
				case 6:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(0,1,'L');break;
				case 7:a(0,1,'L'),a(0,0,'L'),a(1,3,'L'),a(0,2,'L'),a(0,3,'L');break;
				case 8:a(0,0,'L'),a(1,0,'L'),a(2,0,'L'),a(3,0,'L'),a(3,-1,'L');break;
			}break;
	}
	return;
}
void dfs(int step)
{
	bool flag=1;
	for(int i=1;i<=12;i++)
		if(v[i]==0)
			flag=0;
	if(flag)
	{
		for(int i=1;i<=10;i++)
		{
			for(int j=1;j<=i;j++)
				cout<<a[i][j];
			cout<<endl;
		}
		exit(0);
	}
	tal++;
	if(tal>2500000)
		printf("No solution"),exit(0);
	int x,y;
	for(x=1;x<=10;x++)
		for(y=1;y<=x;y++)
			if(a[x][y]=='.')
				goto end;
	end:
	for(int i=1;i<=12;i++)
		if(v[i]==0)
		{
			v[i]=1;
			for(int j=1;j<=num[i];j++)
				if(check(i,j,x,y))
				{
					seter(i,j,x,y);
					dfs(step+1);
					clean(i,j,x,y);
				}
					
			v[i]=0;
		}
}
int main()
{ 
	for(int i=1;i<=10;i++)
		for(int j=1;j<=i;j++)
			cin>>a[i][j],v[a[i][j]-'A'+1]=1;
	dfs(0);
	printf("No solution");
	return 0;
}//403 行的代码结束

---

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/5dfc913c8d8d/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 暴搜 毒瘤题

最后更新：2023-08-21, 23:18:20

上一页 下一页

By Yurchiu.

随机文章回味旧文

2021，初中毕业

一个 4 人囚徒困境的必胜策略

AFO 有感

2020 新年贺词

ASCII 艺术

BSGS 与 exBSGS

CSP-J1 游记

最近更新旧文更新

[Works] 自白 终章

《幽默报 10》

AFO 有感

OI 之旅

《幽默报》

[Works] 自白

[Idea] 试卷排序

其他物件杂物收纳

Hitokoto

Yurchiu 说，除了她以外的人都很强！嘤嘤嘤~~

博客信息

文章数目

158

最近更新

08-21

本站字数

350.6k

文章目录

©2019-2023 Yurchiu. All rights reserved.

Theme Cutie, by Yurchiu.