当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
2032：Square Carpets
题目描述
Mr. Frugal bought a new house. He feels deeply in love with his new house because it has a comfortable living room in which he can put himself completely at ease. He thinks his new house is a really good buy.
But, to his disappointment, the floor of its living room has some scratches on it.
The floor has a rectangle shape, covered with square panels. He wants to replace all the scratched panels with flawless panels, but he cannot afford to do so. Then, he decides to cover all the scratched panels with carpets.
The features of the carpets he can use are as follows.
> Carpets are square-shaped.
> Carpets may overlap each other.
> Carpets cannot be folded.
> Different sizes of carpets are available. Lengths of sides of carpets are multiples of that of the panels.
The carpets must cover all the scratched panels, but must not cover any of the flawless ones.
For example, if the scratched panels are as shown in Figure 1, at least 6 carpets are needed.
Figure 1: Example Covering
As carpets cost the same irrespective of their sizes, Mr. Frugal would like to use as few number of carpets as possible.
Your job is to write a program which tells the minimum number of the carpets to cover all the scratched panels.
But, to his disappointment, the floor of its living room has some scratches on it.
The floor has a rectangle shape, covered with square panels. He wants to replace all the scratched panels with flawless panels, but he cannot afford to do so. Then, he decides to cover all the scratched panels with carpets.
The features of the carpets he can use are as follows.
> Carpets are square-shaped.
> Carpets may overlap each other.
> Carpets cannot be folded.
> Different sizes of carpets are available. Lengths of sides of carpets are multiples of that of the panels.
The carpets must cover all the scratched panels, but must not cover any of the flawless ones.
For example, if the scratched panels are as shown in Figure 1, at least 6 carpets are needed.
Figure 1: Example Covering
As carpets cost the same irrespective of their sizes, Mr. Frugal would like to use as few number of carpets as possible.
Your job is to write a program which tells the minimum number of the carpets to cover all the scratched panels.
输入解释
The input consists of multiple data sets. As in the following, the end of the input is indicated by a line containing two zeros.
DataSet1
DataSet2
...
DataSetn
0 0
Each data set (DataSeti) represents the state of a floor. The format of a data set is as follows.
W H
P11 P12 P13 ... P1W
P21 P22 P23 ... P2W
...
PH1 PH2 PH3 ... PHW
The positive integers W and H are the numbers of panels on the living room in the x- and y- direction, respectively. The values of W and H are no more than 10. The integer Pyx represents the state of the panel. The value of Pyx means,
0: flawless panel (must not be covered),
1: scratched panel (must be covered).
DataSet1
DataSet2
...
DataSetn
0 0
Each data set (DataSeti) represents the state of a floor. The format of a data set is as follows.
W H
P11 P12 P13 ... P1W
P21 P22 P23 ... P2W
...
PH1 PH2 PH3 ... PHW
The positive integers W and H are the numbers of panels on the living room in the x- and y- direction, respectively. The values of W and H are no more than 10. The integer Pyx represents the state of the panel. The value of Pyx means,
0: flawless panel (must not be covered),
1: scratched panel (must be covered).
输出解释
For each data set, your program should output a line containing one integer which represents the minimum number of the carpets to cover all of the scratched panels.
输入样例
4 3 0 1 1 1 1 1 1 1 1 1 1 1 8 5 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 8 8 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0
输出样例
2 6 14 29
最后修改于 2020-10-29T06:21:08+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 1000 | 30000 |
登陆或注册以提交代码