prithivMLmods/Coder-Stat

1 2 3 4<H1>Square Carpets</H1>5 6<P>7Mr. Frugal bought a new house.8He feels deeply in love with his new house9because it has a comfortable living room10in which he can put himself completely at ease.11He thinks his new house is a really good buy.12</P>13 14<P>15But, to his disappointment, 16the floor of its living room has some scratches on it.17</P>18 19<P>20The floor has a rectangle shape, covered with square panels.21He wants to replace all the scratched panels with flawless panels, 22but he cannot afford to do so.23Then, he decides to cover all the scratched panels 24with carpets.25</P>26 27<P>28The features of the carpets he can use are as follows.29</P>30 31<OL>32<LI> Carpets are square-shaped.33<LI> Carpets may overlap each other.34<LI> Carpets cannot be folded.35<LI> Different sizes of carpets are available.36Lengths of sides of carpets are multiples of that of the panels.37</OL>38 39<P>40The carpets must cover all the scratched panels,41but must not cover any of the flawless ones.42</P>43 44<P>45For example, 46if the scratched panels are as shown in Figure 1, 47at least 6 carpets are needed.48</P>49 50<CENTER>51<TABLE>52<TR>53  <TD ALIGN="center"><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_carpets"></TD>54</TR>55<TR>56  <TD ALIGN="center">Figure 1: Example Covering</TD>57</TR>58</TABLE>59</CENTER>60 61<P>62As carpets cost the same irrespective of their sizes, 63Mr. Frugal would like to use as few number of carpets as possible.64</P>65 66<P>67Your job is to write a program which tells the minimum number 68of the carpets to cover all the scratched panels.69</P>70 71 72<H2>Input</H2>73 74<P>75The input consists of multiple data sets.76 77As in the following, the end of the input is indicated by a line78containing two zeros.79</P>80 81 82<BLOCKQUOTE>83<I>DataSet</I><SUB>1</SUB><BR>84<I>DataSet</I><SUB>2</SUB><BR>85...<BR>86<I>DataSet</I><SUB><I>n</I></SUB><BR>87<TT>0</TT> <TT>0</TT>88</BLOCKQUOTE>89 90 91<P>92Each data set (<I>DataSet</I><SUB><I>i</I></SUB>) represents the93state of a floor. The format of a data set is as follows.94</P>95 96<BLOCKQUOTE>97<I>W</I> <I>H</I><BR>98<I>P</I><SUB>11</SUB> <I>P</I><SUB>12</SUB> <I>P</I><SUB>13</SUB> ... <I>P</I><SUB>1<I>W</I></SUB><BR>99<I>P</I><SUB>21</SUB> <I>P</I><SUB>22</SUB> <I>P</I><SUB>23</SUB> ... <I>P</I><SUB>2<I>W</I></SUB><BR>100...<BR>101<I>P</I><SUB><I>H</I>1</SUB> <I>P</I><SUB><I>H</I>2</SUB>102<I>P</I><SUB><I>H</I>3</SUB> ... <I>P</I><SUB><I>HW</I></SUB><BR>103</BLOCKQUOTE>104 105 106<P>107The positive integers <I>W</I> and <I>H</I> are the numbers of panels108on the living room109in the x- and y- direction, respectively.110The values of <I>W</I> and <I>H</I> are no more than 10.111The integer <I>P</I><SUB><I>yx</I></SUB> represents the state of the panel.112The value of <I>P</I><SUB><I>yx</I></SUB> means,113</P>114 115<BLOCKQUOTE>116<TT>0</TT>: flawless panel (must not be covered),<BR>117<TT>1</TT>: scratched panel (must be covered). 118</BLOCKQUOTE>119 120 121<H2>Output</H2>122 123<P>124For each data set,125your program should output a line containing one integer which 126represents the minimum number of the carpets to cover 127all of the scratched panels.128</P>129 130<H2>Sample Input</H2>131<PRE>1324 31330 1 1 11341 1 1 11351 1 1 11368 51370 1 1 1 1 1 1 11381 1 1 1 1 1 1 11391 1 1 1 1 1 1 11401 1 1 0 1 1 1 11410 1 1 1 0 1 1 11428 81430 1 1 0 0 1 1 01441 1 1 1 1 1 1 11451 1 1 1 1 1 1 11460 1 1 0 0 1 1 01470 1 1 0 0 1 1 01481 1 1 1 1 1 1 11491 1 1 1 1 1 1 11500 1 1 0 0 1 1 015110 101521 1 1 1 1 1 1 1 1 11531 1 1 1 1 1 1 1 1 11541 1 0 1 1 0 1 1 0 11551 1 1 1 1 1 1 1 1 11561 1 1 1 1 1 1 1 1 11571 1 0 1 1 0 1 1 0 11581 1 1 1 1 1 1 1 1 11591 1 1 1 1 1 1 1 1 11601 1 0 1 1 0 1 1 0 11611 1 1 1 1 1 1 1 1 11620 0163</PRE>164 165 166<H2>Output for the Sample Input</H2>167 168<PRE>169217061711417229173</PRE>174 175 176