パズル的な問題に関する疑問

いま、こういう問題にぶつかっている。

1マスが1cmの方眼紙があったとして、そのマスをいくつか塗って作られた図形があるとする。で、それを幅1cmのテープで重複無く、すきまなく覆いたいとする。テープは１ロールあって、長さは十分、で、1cmの倍数のところで切って、1cm x Ncmの長方形を作っていく。

問題は、テープを切る回数を最小にする方法を求めよ。というもの。

凸図形だったらかんたんで、縦と横の長さのうち小さい方となる。

□□□■□□

□■■■■□

■■■■■■

□■■■□□

凸図形の例。テープを４回切ると覆える。じつは凸多角形ではないんだが、言わんとすることを察して欲しい。多分■部分が単調に増加してその後単調に減少するとかそういうの。そういえばそもそも凸という漢字は全然凸多角形じゃないな。

□■□■□□

□■■■■□

■■■■■■

□■■■□□

凸図形ではない例。テープを５回切る必要が出てくる。

凸図形ではない場合に、最小回数を求めるアルゴリズムはあるんだろうか。

あと興味があるのは、テープの切り方を整数倍とかではなく、まったく自由にした場合、回数を節約できる場合があるだろうか？折れ線、曲線を切り出しても切断回数は１回。とにかく、N個の連続な図形を切り出したらカットはN回とする。つまり、境界でジャンプするようにして、鋏の軌跡は一筆書きだが複数の図形を切り出すようなテクニックは認められない。テープは裏返してもOK。もちろん、曲線を切り出した以上、責任もってうまく噛み合わせて、与えられた方眼図形が重複無くすきまなく覆えるようにしないといけない。