题解：P10313 [SHUPC 2024] 占地斗士！

zhengpie · 2024-04-10 17:08:54 · 题解

题目传送门

1.思路

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

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

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

现在开始讲如何深搜。首先我们考虑每个图形左上角的点，设他为 a_{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 里不可以传入 a_{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的好习惯
}

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

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

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

3.完整代码

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

//样例输入#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.题外话

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