1 条题解

  • 0
    @ 2025-8-24 22:56:50

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar zhengpie
    天降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行指乱其所为，所以动心忍性，曾益其所不能。

    搬运于2025-08-24 22:56:50，当前版本为作者最后更新于2024-04-10 17:08:54，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    题目传送门

    1.思路

    看到这道题，我的第一反应就是搜索题，但是是深搜还是广搜呢？

    答案是深搜。（虽然一开始我一直再想广搜）如果用广搜的话，对于下面这组数据就会超时（当然是不加很牛的剪枝的）：

    //样例输入#3
10 10
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
//样例输出#3
18

    现在开始讲如何深搜。首先我们考虑每个图形左上角的点，设他为 ai,ja_{i,j}。以第一个图形为例(这里图形的顺序以题目中给的四张图为准)，如果想要摆放上第一个图形，就必须让下列条件成立：

    if(a[i][j] == '.' && a[i][j + 2] == '.' && a[i + 2][j] == '.' && a[i + 1][j + 1] == '.' && a[i + 2][j + 2] == '.')

    同样的，下面分别给出让第二，三，四个图形可以摆放的条件：

    //2号图
if(a[i][j + 1] == '.' && a[1 + i][j] == '.' && a[i + 2][j + 1] == '.' && a[i + 1][j + 2] == '.')
//3号图
if(a[i][j] == '.' && a[i][j + 1] == '.' && a[i + 1][j] == '.' && a[i + 1][j + 1] == '.' )
//4号图
if(a[i][j + 1] == '.' && a[1 + i][j] == '.' && a[i + 2][j + 1] == '.' && a[i + 1][j + 2] == '.' && a[i + 1][j + 1] == '.')

    2.细节

    首先注意到 DFS 里不可以传入 ai,ja_{i,j} 这样的二维数组，所以我们定义一个结构体 ground 来记录：

    struct ground
{
	char a[15][15];
	int cnt;//记录当前占领的格子的个数
	bool c1,c2,c3,c4;//因为题目说每个图形都只能用一次，所以用他们来记录这些东西用没用过。
}g;//g记录初始地图

    然后，不难写出 DFS：

    void dfs(ground u)
{
	if(u.cnt >= maxn) maxn = u.cnt;//更新maxn
	for(int i = 1;i <= n - 2;i++)//注意是n - 2，因为是3 * 3 的格子，而i，j表示的是左上角的点，所以这两重循环只能处理1,2,4号图。
		for(int j = 1;j <= m - 2;j++)
		{
			if(u.a[i][j] == '.' && u.a[i][j + 2] == '.' && u.a[i + 2][j] == '.' && u.a[i + 1][j + 1] == '.' && u.a[i + 2][j + 2] == '.' && u.c1 != 1)//1号图
			{
				u.a[i][j] = u.a[i][j + 2] = u.a[i + 2][j] = u.a[i + 1][j + 1] = u.a[2 + i][j + 2] = '#';
				u.c1 = 1;//记得标记！
				u.cnt += 5;
				dfs(u);
				u.c1 = 0;//类似回溯的技巧，因为后面的图可能还要用这个u，所以得给后面的用初始数据
				u.cnt -= 5;
				u.a[i][j] = u.a[i][j + 2] = u.a[i + 2][j] = u.a[i + 1][j + 1] = u.a[2 + i][j + 2] = '.';
			}
			if(u.a[i][j + 1] == '.' && u.a[1 + i][j] == '.' && u.a[i + 2][j + 1] == '.' && u.a[i + 1][j + 2] == '.' && u.c2 != 1)//2号图
			{
				u.a[i][j + 1] = '#';u.a[1 + i][j] = '#';u.a[i + 2][j + 1] = '#';u.a[i + 1][j + 2] = '#';
				u.cnt += 4;//复制1号图的代码时，记得2号图只占了4个格子！
				u.c2 = 1;
				dfs(u);
				u.c2 = 0;//同1号图
				u.cnt -= 4;
				u.a[i][j + 1] = '.';u.a[1 + i][j] = '.';u.a[i + 2][j + 1] = '.';u.a[i + 1][j + 2] = '.';
			}
			if(u.a[i][j + 1] == '.' && u.a[1 + i][j] == '.' && u.a[i + 2][j + 1] == '.' && u.a[i + 1][j + 2] == '.' && u.a[i + 1][j + 1] == '.' && u.c4 != 1)//注意是4号图,上面已经讲过了这两重循环不处理3号图
			{
				u.a[i][j + 1] = '#';u.a[1 + i][j] = '#';u.a[i + 2][j + 1] = '#';u.a[i + 1][j + 2] = '#';u.a[i + 1][j + 1] = '#';
				u.c4 = 1;
				u.cnt += 5;
				dfs(u);
				u.cnt -= 5;//同1号图
				u.c4 = 0;
				u.a[i][j + 1] = '.';u.a[1 + i][j] = '.';u.a[i + 2][j + 1] = '.';u.a[i + 1][j + 2] = '.';u.a[i + 1][j + 1] = '.';
			}
		}
	for(int i = 1;i <= n - 1;i++)//这两重循环处理三号图，因为3号图是2 * 2的，所以i枚举到n - 1
		for(int j = 1;j <= m - 1;j++)//同理，枚举到m - 1
		{
			if(u.a[i][j] == '.' && u.a[i][j + 1] == '.' && u.a[i + 1][j] == '.' && u.a[i + 1][j + 1] == '.' && u.c3 != 1)
			{
				u.a[i][j] = '#';u.a[i][j + 1] = '#';u.a[i + 1][j] = '#';u.a[i + 1][j + 1] = '#';
				u.cnt += 4;
				u.c3 = 1;
				dfs(u);
				u.c3 = 0;//同一号图
				u.cnt -= 4;
				u.a[i][j] = '.';u.a[i][j + 1] = '.';u.a[i + 1][j] = '.';u.a[i + 1][j + 1] = '.';
			}
		}
	return;//养成return的好习惯
}

    然后，放到上面，看一看我们的样例输入输出 33，把他复制下来，发现超时了！怎么剪枝？

    观察题目，可以知道，由于每个图都只能用一次，所以最大就只能输出 (5+4+5+4=)18(5 + 4 + 5 + 4 = )18，也就是说，当 maxn 达到 1818 时，就直接跳出函数。所以，我们在 DFS 中补上下面的代码：

    if(maxn == 18) 
{
	cout<<18;
	exit(0);//相当于主函数中的return 0，但如果在自定义函数中return 0，无法达到结束程序的效果，所以使用exit()函数
}

    3.完整代码

    在给完整代码之前，先再附上一个东西：样例输入输出 44！

    //样例输入#4
9 7
.#.#...
..#....
..##.#.
##.#...
......#
##.#..#
###.#..
...##..
.#.#...
//样例输出#4
14

    最后，附上完整代码，请放心食用！

    #include<bits/stdc++.h>
using namespace std;
#define int long long
struct ground
{
	char a[15][15];
	int cnt;//记录当前占领的格子的个数
	bool c1,c2,c3,c4;//因为题目说每个图形都只能用一次，所以用他们来记录这些东西用没用过。
}g;//g记录初始地图
int n,m,maxn;
void dfs(ground u)
{
	if(maxn == 18) 
	{
		cout<<18;
		exit(0);//相当于主函数中的return 0，但如果在自定义函数中return 0，无法达到结束程序的效果，所以使用exit()函数
	}
  	if(u.cnt >= maxn) maxn = u.cnt;//更新maxn
	for(int i = 1;i <= n - 2;i++)//注意是n - 2，因为是3 * 3 的格子，而i，j表示的是左上角的点，所以这两重循环只能处理1,2,4号图。
		for(int j = 1;j <= m - 2;j++)
		{
			if(u.a[i][j] == '.' && u.a[i][j + 2] == '.' && u.a[i + 2][j] == '.' && u.a[i + 1][j + 1] == '.' && u.a[i + 2][j + 2] == '.' && u.c1 != 1)//1号图
			{
				u.a[i][j] = u.a[i][j + 2] = u.a[i + 2][j] = u.a[i + 1][j + 1] = u.a[2 + i][j + 2] = '#';
				u.c1 = 1;//记得标记！
				u.cnt += 5;
				dfs(u);
				u.c1 = 0;//类似回溯的技巧，因为后面的图可能还要用这个u，所以得给后面的用初始数据
				u.cnt -= 5;
				u.a[i][j] = u.a[i][j + 2] = u.a[i + 2][j] = u.a[i + 1][j + 1] = u.a[2 + i][j + 2] = '.';
			}
			if(u.a[i][j + 1] == '.' && u.a[1 + i][j] == '.' && u.a[i + 2][j + 1] == '.' && u.a[i + 1][j + 2] == '.' && u.c2 != 1)//2号图
			{
				u.a[i][j + 1] = '#';u.a[1 + i][j] = '#';u.a[i + 2][j + 1] = '#';u.a[i + 1][j + 2] = '#';
				u.cnt += 4;//复制1号图的代码时，记得2号图只占了4个格子！
				u.c2 = 1;
				dfs(u);
				u.c2 = 0;//同1号图
				u.cnt -= 4;
				u.a[i][j + 1] = '.';u.a[1 + i][j] = '.';u.a[i + 2][j + 1] = '.';u.a[i + 1][j + 2] = '.';
			}
			if(u.a[i][j + 1] == '.' && u.a[1 + i][j] == '.' && u.a[i + 2][j + 1] == '.' && u.a[i + 1][j + 2] == '.' && u.a[i + 1][j + 1] == '.' && u.c4 != 1)//注意是4号图,上面已经讲过了这两重循环不处理3号图
			{
				u.a[i][j + 1] = '#';u.a[1 + i][j] = '#';u.a[i + 2][j + 1] = '#';u.a[i + 1][j + 2] = '#';u.a[i + 1][j + 1] = '#';
				u.c4 = 1;
				u.cnt += 5;
				dfs(u);
				u.cnt -= 5;//同1号图
				u.c4 = 0;
				u.a[i][j + 1] = '.';u.a[1 + i][j] = '.';u.a[i + 2][j + 1] = '.';u.a[i + 1][j + 2] = '.';u.a[i + 1][j + 1] = '.';
			}
		}
	for(int i = 1;i <= n - 1;i++)//这两重循环处理三号图，因为3号图是2 * 2的，所以i枚举到n - 1
		for(int j = 1;j <= m - 1;j++)//同理，枚举到m - 1
		{
			if(u.a[i][j] == '.' && u.a[i][j + 1] == '.' && u.a[i + 1][j] == '.' && u.a[i + 1][j + 1] == '.' && u.c3 != 1)
			{
				u.a[i][j] = '#';u.a[i][j + 1] = '#';u.a[i + 1][j] = '#';u.a[i + 1][j + 1] = '#';
				u.cnt += 4;
				u.c3 = 1;
				dfs(u);
				u.c3 = 0;//同一号图
				u.cnt -= 4;
				u.a[i][j] = '.';u.a[i][j + 1] = '.';u.a[i + 1][j] = '.';u.a[i + 1][j + 1] = '.';
			}
		}
	return;//养成return的好习惯
}
signed main()
{
	ios::sync_with_stdio(0);g.cnt = 0;g.c1 = 0;g.c2 = 0;g.c3 = 0;g.c4 = 0;//初始化
	cin>>n>>m;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++) cin>>g.a[i][j];
	dfs(g);
	cout<<maxn;
	
	return 0;
}

    4.题外话

    这里给的啥样例啊，弱的要死，还得我自己造样例！

    • 1

    [SHUPC 2024] 占地斗士！

    信息

    ID
    10010
    时间
    2000ms
    内存
    512MiB
    难度
    2
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 19ms