题解：AT_abc345_d [ABC345D] Tiling

· · 题解

ABC345D：搜索剪枝

有一篇题解使用折半搜索解决这道题，方法值得学习。我写一篇用搜索剪枝解决这道题的题解。

搜索部分

数据范围很小，尝试用搜索解决。
考虑深度优先搜索，dfs(x) 表示当前放置第 x 个矩形，枚举不放这个矩形，或者这个矩形放的位置。位置要满足这个矩形所覆盖的位置都没有被其他矩形覆盖。然后把这个矩形放下来，搜索下一个矩形。回溯时，从棋盘上拿掉这个矩形。注意矩形可以旋转。最后进行判断，整个棋盘都被覆盖就说明找到解。
以上深度优先搜索的步骤写成代码如下： 


pair<int, int> a[10];                                 // 矩形大小
bool vis[10][10];                                     // 是否放置了矩形
void down(int xl, int xr, int yl, int yr, bool state) // 放置或拿掉矩形
{
    for (int hc = xl; hc <= xr; hc++)
        for (int wc = yl; wc <= yr; wc++)
            vis[hc][wc] = state;
}
bool dfs(int x)
{
    if (x == n + 1) // 搜索完成
    {
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++)
                if (!vis[i][j])
                    return false;
        return true;
    }
    if (dfs(x + 1)) return true; // 不选这个矩形
    int hh = a[x].first, ww = a[x].second;
    for (int i = 1; i + hh - 1 <= h; i++) // 枚举放的位置
        for (int j = 1; j + ww - 1 <= w; j++)
        {
            bool flag = 1;
            for (int hc = i; flag && (hc <= i + hh - 1); hc++)
                for (int wc = j; flag && (wc <= j + ww - 1); wc++)
                    flag &= !vis[hc][wc];
            if (!flag)
                continue;
            down(i, i + hh - 1, j, j + ww - 1, true);
            if (dfs(x + 1))
                return true;
            down(i, i + hh - 1, j, j + ww - 1, false); // 回溯
        }
    swap(hh, ww); // 旋转
    for (int i = 1; i + hh - 1 <= h; i++)
        for (int j = 1; j + ww - 1 <= w; j++)
        {
            bool flag = 1;
            for (int hc = i; flag && (hc <= i + hh - 1); hc++)
                for (int wc = j; flag && (wc <= j + ww - 1); wc++)
                    flag &= !vis[hc][wc];
            if (!flag)
                continue;
            down(i, i + hh - 1, j, j + ww - 1, true);
            if (dfs(x + 1))
                return true;
            down(i, i + hh - 1, j, j + ww - 1, false);
        }
    return false;
}

时间复杂度分析：n 个矩形，每个矩形选或不选共有 2^n 种方案，每种方案的判断需要枚举每个矩形放的位置，随着放的矩形越来越多可选方案数会越来越少，增长方式类似阶乘但是低于阶乘。
总而言之时间复杂度过高，容易超时，考虑剪枝优化。

可行性剪枝

容易发现，在共 2^n 种方案中，大部分方案是可以容易判断不可行的。例如，把所选矩形的面积相加，若面积不等于整个棋盘的面积则一定不可行，可以直接剪枝。
以样例 #1 为例，在 2^5 = 32 种方案中，只有两种方案满足面积相加等于整个棋盘面积，搜索范围大大减少，剪枝行之有效。
具体地，可以在开始搜索前二进制枚举选哪些矩形，再计算面积来判断是否一定不可行。
二进制枚举的代码实现如下：

vector<int> card; // 选的矩形
int get_bit(int x, int id) // 获取集合 x 二进制表示的第 id 位
{
    return (x >> (id - 1)) & 1;
}
bool check(int o)
{
    int area = 0; // 选的矩形的面积和
    card.clear();
    for (int i = 1; i <= n; i++)
        if (get_bit(o, i))
            card.push_back(i), area += a[i].first * a[i].second;
    if (area != h * w) // 一定不可行
        return false;
    memset(vis, 0, sizeof vis);
    return dfs(0);
}

搜索顺序

显然矩形的放置顺序不影响求解问题。
在枚举矩形放的位置的时候，若先放大的矩形，则后面矩形可以选的位置就少了，搜索树就会窄很多。
所以，我们可以对所有矩形按面积从大到小排序，再搜索求解问题。 

using pii = pair<int, int>;
sort(a + 1, a + 1 + n, [&](pii x, pii y) { return x.first * x.second > y.first * y.second; });

最终代码

将搜索与剪枝结合起来，就可以通过这题。参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, h, w;
using pii = pair<int, int>;

pii a[10];        // 矩形大小
bool vis[10][10]; // 是否放置了矩形

void down(int xl, int xr, int yl, int yr, bool state) // 放置或拿掉矩形
{
    for (int hc = xl; hc <= xr; hc++)
        for (int wc = yl; wc <= yr; wc++)
            vis[hc][wc] = state;
}

vector<int> card; // 选的矩形
bool dfs(int x)
{
    if (x == card.size()) // 搜索完成
    {
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++)
                if (!vis[i][j])
                    return false;
        return true;
    }
    int hh = a[card[x]].first, ww = a[card[x]].second;
    for (int i = 1; i + hh - 1 <= h; i++) // 枚举放的位置
        for (int j = 1; j + ww - 1 <= w; j++)
        {
            bool flag = 1;
            for (int hc = i; flag && (hc <= i + hh - 1); hc++)
                for (int wc = j; flag && (wc <= j + ww - 1); wc++)
                    flag &= !vis[hc][wc];
            if (!flag)
                continue;
            down(i, i + hh - 1, j, j + ww - 1, true);
            if (dfs(x + 1))
                return true;
            down(i, i + hh - 1, j, j + ww - 1, false); // 回溯
        }
    swap(hh, ww); // 旋转
    for (int i = 1; i + hh - 1 <= h; i++)
        for (int j = 1; j + ww - 1 <= w; j++)
        {
            bool flag = 1;
            for (int hc = i; flag && (hc <= i + hh - 1); hc++)
                for (int wc = j; flag && (wc <= j + ww - 1); wc++)
                    flag &= !vis[hc][wc];
            if (!flag)
                continue;
            down(i, i + hh - 1, j, j + ww - 1, true);
            if (dfs(x + 1))
                return true;
            down(i, i + hh - 1, j, j + ww - 1, false);
        }
    return false;
}

int get_bit(int x, int id) // 获取集合 x 二进制表示的第 id 位
{
    return (x >> (id - 1)) & 1;
}
bool check(int o)
{
    int area = 0;
    card.clear();
    for (int i = 1; i <= n; i++)
        if (get_bit(o, i))
            card.push_back(i), area += a[i].first * a[i].second;
    if (area != h * w) // 一定不可行
        return false;
    memset(vis, 0, sizeof vis);
    return dfs(0);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> h >> w;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first >> a[i].second;
    sort(a + 1, a + 1 + n, [&](pii x, pii y) { return x.first * x.second > y.first * y.second; });
    for (int o = 1; o < 1 << n; o++)
        if (check(o))
        {
            cout << "Yes" << endl;
            return 0;
        }
    cout << "No" << endl;
    return 0;
}

总结

在搜索问题中，可行性剪枝和适当改变搜索顺序都可以有效提升程序效率。给不熟悉搜索剪枝的同学推荐一道经典例题：P1120 小木棍