放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

POJ 2032 Square Carpets 题解《挑战程序设计竞赛》

目录

Square Carpets.jpg挑战程序设计竞赛第二版.jpg

POJ 2032 Square Carpets 

铺地毯:用最少的正方形覆盖所有点。

Square Carpets.jpg

4.5开动脑筋智慧搜索 

A*与IDA* 

大致思路是预处理出一个覆盖所有点的正方形集合,最优解下界为所有点恰好能被最大正方形覆盖,然后IDA*搜索。

首先预处理,求出以某点为右下角的正方形最大边长。对于上图,该矩阵为

0 1 1 1 1 1 1 1 
1 1 2 2 2 2 2 2 
1 2 2 3 3 3 3 3 
1 2 3 0 1 2 3 4 
0 1 2 1 0 1 2 3

进一步,若某个正方形完全包含在另一个正方形中,则排除这个正方形,因为我们要尽量少用正方形。

2032.png

上图绿色正方形完全覆盖红色正方形,所以去掉红色正方形。去掉的操作很方便,简单将该元素设为0即可。

这一步得到:

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 3 3 3 0 0 
0 0 3 0 0 0 0 4 
0 0 2 1 0 0 0 3

接着统计每个点被几个正方形覆盖:

0 1 2 3 3 2 1 1 
1 2 3 3 3 2 1 1 
1 2 3 3 3 3 2 2 
1 2 2 0 1 2 2 2 
0 1 1 1 0 1 1 1

如果某个点只被一个正方形覆盖,则该正方形必选,记录下来;否则将该正方形加入搜索列表,从右下角往左上角搜索。

下界函数可以用这么一个简单的假设:将坏点视作流动的散沙,总能根据正方形变换形状,最后紧凑地流入一个个最大正方形中,返回用多少个最大正方形容器能够放得下剩余坏点,该数目即为当前情况下的最优解下界。

最后就是IDA*搜索了,这还算一道蛮能体现IDA*思想的题目。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
#define MAX_N 10

int ans, H, W, limit,           // 最优解
        max_w;           // 正方形最大边长
int T[MAX_N][MAX_N], // T[y][x] := 以(x,y)为右下角的正方形最大边长
        F[MAX_N][MAX_N], // 输入
        X[MAX_N][MAX_N]; // 每个点被几个正方形覆盖
vector<pair<int, int> > v;  // 正方形的右下角坐标

bool is_solved()
{
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if (F[i][j] && X[i][j] == 0)
            {
                return false;
            }
        }
    }
    return true;
}

/**
 * 当前所需正方形的下界
 * @return
 */
int h()
{
    int sum = 0;
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if (F[i][j] && X[i][j] == 0)
            {
                sum++;// 需要覆盖但还没覆盖的点数
            }
        }
    }
    return sum / (max_w * max_w);   // 假设这些点极其紧凑,形成一个个最大正方形
}

/**
 * 搜索
 * @param s 当前状态搜索的正方形个数
 * @param cost 当前正方形个数
 * @return 是否可行
 */
bool dfs(int s, int cost)
{
    if (is_solved())
        return true;
    if (s >= v.size())
        return false;
    if (cost + h() >= limit)
        return false;

    for (int i = v[s].first + 1; i < H; i++)
    {
        for (int j = 0; j < W; ++j)
        {
            if (F[i][j] && X[i][j] == 0)
                return false;
        }
    }

    if (dfs(s + 1, cost))   // 不要s这个正方形
        return true;
    // 要s这个正方形
    int X_backup[MAX_N][MAX_N];
    memcpy(X_backup, X, sizeof(X));
    int pi = v[s].first;
    int pj = v[s].second;
    int w = T[pi][pj];
    for (int y = pi - w + 1; y <= pi; ++y)
    {
        for (int x = pj - w + 1; x <= pj; ++x)
        {
            X[y][x]++;
        }
    }

    if (dfs(s + 1, cost + 1)) // 所以花费正方形个数+1
        return true;
    memcpy(X, X_backup, sizeof(X));
    return false;
}

int ida_star()
{
    if (max_w == 0)
        return 0;
    for (limit = h(); limit < 100; limit++)
    {
        if (dfs(0, 0))
            return limit;
    }
}

void init()
{
    memset(T, 0, sizeof(T));
    memset(X, 0, sizeof(X));
    for (int i = 0; i < H; ++i)
    {
        T[i][0] = F[i][0];
    }
    for (int j = 0; j < W; ++j)
    {
        T[0][j] = F[0][j];
    }

    for (int i = 1; i <= H - 1; ++i)
    {
        for (int j = 1; j <= W - 1; ++j)
        {
            if (F[i][j])
            {
                T[i][j] = min(T[i - 1][j - 1], min(T[i - 1][j], T[i][j - 1])) + 1;
            }
            else
            {
                T[i][j] = 0;
            }
        }
    }

    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            int w = T[i][j];    // 最大正方形边长
            for (int pi = i - (w - 1); pi <= i; ++pi)
            {
                for (int pj = j - (w - 1); pj <= j; ++pj)
                {
                    if (i == pi && j == pj)         // 遍历包含的某个正方形
                        continue;
                    int l = max(i - pi, j - pj);    // 包含的某个正方形边长
                    if (w - l >= T[pi][pj])
                    {
                        T[pi][pj] = 0;              // 完全包含,排除
                    }
                }
            }
        }
    }
    int K[MAX_N][MAX_N]; // 每个点被几个正方形覆盖
    memset(K, 0, sizeof(K));
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if (T[i][j])
            {
                for (int y = i - T[i][j] + 1; y <= i; ++y)
                {
                    for (int x = j - T[i][j] + 1; x <= j; ++x)
                    {
                        K[y][x]++;
                    }
                }
            }
        }
    }
    v.clear();
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if (T[i][j])
            {
                for (int y = i - T[i][j] + 1; y <= i; ++y)
                {
                    for (int x = j - T[i][j] + 1; x <= j; ++x)
                    {
                        if (K[y][x] == 1)   // 只被一个正方形覆盖,必选
                        {
                            for (int y = i - T[i][j] + 1; y <= i; ++y)
                            {
                                for (int x = j - T[i][j] + 1; x <= j; ++x)
                                {
                                    X[y][x]++;
                                }
                            }
                            ans++;
                            T[i][j] = 0;
                            goto OUTER;
                        }
                    }
                }
            }
            OUTER:;
        }
    }
    max_w = 0;
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if (T[i][j])
            {
                max_w = max(max_w, T[i][j]);
                v.push_back(make_pair(i, j));
            }
        }
    }
    reverse(v.begin(), v.end());    // 从右下角往左上角搜索
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d%d", &W, &H), W)
    {
        for (int i = 0; i < H; ++i)
        {
            for (int j = 0; j < W; ++j)
            {
                scanf("%d", &F[i][j]);
            }
        }
        ans = 0;
        init();
        printf("%d\n", ida_star() + ans);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
16519210 hankcs 2032 Accepted 196K 0MS C++ 5008B 2017-01-25 11:07:12

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2032 Square Carpets 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机