当前位置：首页 > web >正文

算法题（170）：地毯填补问题

web 2025/6/16 6:58:39

审题：

本题需要我们找出地毯的铺设方式并将铺设方式打印出来

要求：

1.地毯不能互相覆盖

2.地毯不能铺设到障碍物（公主）

3.地毯必须铺满地（除了公主所在位置）

4.地毯坐标是拐角的坐标（行为x，列为y）

思路：

方法一：分治

我们不要一上来就直接分析最难的情况，我们先分析k为1的情况

k为1也就是长度为2^1的情况，此时矩阵为2*2

一共有四种情况，我们只需要选择不包含障碍物的地毯即可

然后我们看看k为2的情况

此时我们其实可以将矩阵分为四部分，每部分都是k为1的情况的矩阵，对于包含公主的那一部分我们可以直接利用上情况1的方法，对于其他三部分我们则可以铺设一块恰好包含这三部分的地毯，从而让其他三部分都有障碍物，进而可以完全利用k=1的解决方法解决k=2的问题

而我们的大问题可以分解为同样处理方法的小问题，此时可以用递归算法

递归功能：将对应矩阵的铺设方法打印出来

步骤：

1.根据左上角坐标判断障碍物所在位置，并铺设一块地毯覆盖其他三部分

2.利用递归函数解决如今四部分的地毯填补方案

3.当矩阵长度为1递归回溯

解题：
#include<iostream>
using namespace std;
int k,x,y;
void dfs(int x0, int y0, int len, int x, int y)
{if (len == 1) return;len /= 2;if (x < x0 + len && y < y0 + len)//左上角情况{cout << x0 + len << " " << y0 + len << " " << 1 << endl;//地毯一dfs(x0, y0, len, x, y);dfs(x0, y0 + len, len, x0 + len - 1, y0 + len);dfs(x0 + len, y0, len, x0 + len, y0 + len - 1);dfs(x0 + len, y0 + len, len, x0 + len, y0 + len);}else if (x >= x0 + len && y >= y0 + len)//右下角情况{cout << x0 + len-1 << " " << y0 + len-1 << " " << 4 << endl;//地毯四dfs(x0, y0, len, x0 + len - 1, y0 + len - 1);dfs(x0, y0 + len, len, x0 + len - 1, y0 + len);dfs(x0 + len, y0, len, x0 + len, y0 + len - 1);dfs(x0 + len, y0 + len, len, x, y);}else if (x >= x0 + len)//左下角情况{cout << x0 + len - 1 << " " << y0 + len  << " " << 3 << endl;//地毯三dfs(x0, y0, len, x0 + len - 1, y0 + len - 1);dfs(x0, y0 + len, len, x0 + len - 1, y0 + len);dfs(x0 + len, y0, len, x, y);dfs(x0 + len, y0 + len, len, x0 + len, y0 + len);}else//右上角{cout << x0 + len  << " " << y0 + len -1 << " " << 2 << endl;//地毯三dfs(x0, y0, len, x0 + len - 1, y0 + len - 1);dfs(x0, y0 + len, len, x, y);dfs(x0 + len, y0, len, x0 + len, y0 + len - 1);dfs(x0 + len, y0 + len, len, x0 + len, y0 + len);}return;
}
int main()
{cin >> k >> x >> y;k = (1 << k);//变为2^kdfs(1, 1, k, x, y);//对指定矩阵填补地毯并输出填补数据return 0;
}
P1228 地毯填补问题 - 洛谷