构造算法

Published: by Creative Commons Licence

  • Tags:

二维网格放置1x2和2x1方块问题

有一个n行m列的二维网格,你有a个1x2的方块和b个2x1的方块。问是否可以将这些方块不相互覆盖全部放置到网格上。

这是atcoder的一道题目

这个问题我也没法太清晰地证明,就只是讲讲做法就好了。

首先我们可以很自然地将两个1x2方块或两个2x1方块合并为一个2x2方块,这不是什么难事。

当n和m都是偶数的时候,将2x2的方块往上丢就可以了。

之后考虑当m为奇数的时候,我们可以将最左边那一行先用2x1的方块覆盖。

分两种情况讨论,若n是偶数,那么这意味这最左边那一行可以被完全覆盖(除非$2a<n$)。这种情况下问题就变成了在n行(m-1)列网格放置的问题。

同样如果n是奇数、m是偶数,问题也是同样解决。

下面说一下n是奇数、m是偶数的情况下。这时候不管如何放置都会出现至少一个空位。我们先将最左边那一列用2x1的方块覆盖,最上面的那一列用1x2的方块覆盖,当然我们最后一定会留出至少一个空位,推荐将空位让给第3行第1列。比如考虑5行3列的情况。

^<>
v..
...
^..
v..

我们要的效果就是这样。说一下这样的好处。当剩下的a和b都是奇数的情况下,原先我们会浪费1个2x2的空格。

^<>
v<>
...
^^.
vv.

但是,这里我们可以避免2x2空格的浪费,考虑下面的方法:

^<>
v.^
<>v
^..
v..

因此,当a为4,b为3的时候,正确的做法如下:

^<>
v.^
<>v
^<>
v<>