铺地毯:用最少的正方形覆盖所有点。
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
进一步,若某个正方形完全包含在另一个正方形中,则排除这个正方形,因为我们要尽量少用正方形。
上图绿色正方形完全覆盖红色正方形,所以去掉红色正方形。去掉的操作很方便,简单将该元素设为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 题解《挑战程序设计竞赛》