给定一个 n×n 的矩形,其中从左上角开始,对角线上连续的k 个格子中有障碍物。你可以把若干 1×2 的小矩形放置到该大矩形中,要求是放置的两个小矩形不能占据相同的格子,且不能碰到障碍物。给定 n,k,请你输出一个方案,使得放置的 1×2 小矩形尽可能多。c++代码
时间: 2024-02-11 15:07:40 浏览: 42
以下是一个基于贪心算法的C++代码实现,时间复杂度为O(n^2):
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 105;
int n, k;
bool obstacle[MAXN][MAXN]; // 障碍物
bool covered[MAXN][MAXN]; // 标记已被覆盖的位置
int cnt; // 已放置的小矩形数目
int ans[MAXN][2]; // 存储放置的位置
void put(int i, int j) { // 放置一个小矩形
covered[i][j] = covered[i][j+1] = true;
ans[cnt][0] = i;
ans[cnt][1] = j;
cnt++;
}
int main() {
cin >> n >> k;
memset(obstacle, false, sizeof(obstacle));
memset(covered, false, sizeof(covered));
cnt = 0;
// 输入障碍物
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
obstacle[x][y] = true;
}
// 从左上角开始,按行扫描
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!obstacle[i][j] && !covered[i][j]) { // 如果该位置未被障碍物或已被覆盖
if (j < n && !obstacle[i][j+1] && !covered[i][j+1]) { // 如果该位置和右边的位置都未被覆盖
put(i, j); // 放置一个小矩形
} else if (i < n && !obstacle[i+1][j] && !covered[i+1][j]) { // 如果该位置下方的位置未被覆盖
put(i, j); // 放置一个小矩形
}
}
}
}
// 输出结果
cout << cnt << endl;
for (int i = 0; i < cnt; i++) {
cout << ans[i][0] << " " << ans[i][1] << endl;
}
return 0;
}
```
算法思路:
从左上角开始,按行扫描整个矩形。对于每个位置,如果该位置未被障碍物或已被覆盖,且该位置和右边的位置都未被覆盖,则放置一个小矩形覆盖这两个位置。否则,如果该位置下方的位置未被覆盖,则放置一个小矩形覆盖该位置和下方的位置。依此类推,直到整个矩形被覆盖完毕。