別解として、最大二部マッチングに帰着させる解法があるので紹介します。

説明を簡単にするため、以下の解説では上から \(i\) 行目, 左から \(j\) 列目のマスに番号 \(i \times W + j\) を対応させてマス目を整数 1 個で表します。
まず、解法は次の通りです。

解法

\(\lbrace 1, 2, \dots, HW \rbrace\) および \(\lbrace 1', 2', \dots, HW'\rbrace\) を部集合とする \(2HW\) 頂点の二部グラフ \(G\) を考える。
ここで、すべての隣接するマスの組 \((i, j)\) について、マス \(i\) が 2 であり、かつ マス \(j\) が 1 でないときに \(G\) の頂点 \(i\) と 頂点 \(j'\) の間に辺が張られている。
このとき \(G\) の最大マッチングの辺の本数がグリッドに含まれる 2 の個数と一致していれば答えは Yes, そうでない場合は答えは No である。最大マッチングは Dinic 法で \(\mathrm{O}((HW)^{1.5})\) で十分高速に計算できる。

解法の正当性を説明します。

あるマッチングに対して、次の条件を満たす \(x\) を invalid なマス と呼びます。

• 相異なる整数 \(y,z\) があって、頂点 \(x\) は マッチングで \(y'\) と、頂点 \(x'\) は \(z\) と結ばれている。

また、次の条件を満たすマッチングを valid なマッチング と呼びます。

• 辺の数がグリッドに含まれる 2 の個数と一致している。
• invalid な マスが存在しない。

\(G\) が valid なマッチングを含むとき、畳の敷き方は、すべてのマッチングに含まれる辺について 辺の両端を覆う位置に 1x2 の畳を敷き、それ以外のマスに 1x1 の畳を敷けば valid な畳の敷き方になります。逆にすべての valid な畳の敷き方を \(G\) における valid なマッチングに対応させることもできるので(詳細略) 、畳の敷き方の存在判定は \(G\) における valid なマッチングの存在判定と同値です。

最大流が 2 の個数と一致しないときは 明らかに valid なマッチングは存在しません。 一致する場合に必ず valid なマッチングが存在することを証明します。

辺の本数が 2 の個数と一致するマッチング を任意に 1 つ取り \(m\) とします。\(m\) に対して次の一連の操作を \(0\) 回以上作用させます。

• \(m\) が invalid なマスを含まない場合、操作を終了する。invalid なマスがあるとき、1 つ取り \(x\) とする。
• 空の列 \(a\) を用意する。次の操作を繰り返す。
  • \(a\) に \(x\) を追加する。
  • \(a\) に \(x\) が \(2\) 個以上含まれている場合、繰り返しを終了する。
  • マス \(y\) を、頂点 \(x'\) と頂点 \(y\) がマッチングされているようなマスとする。
  • \(y\) が invalid なマスでない場合は、頂点 \(y'\) はマッチングに使用されていない頂点である。よって頂点 \(x\) のマッチング先を \(y'\) に変更して、操作全体を終了する。
    • 注釈：\(x'-y\) 間に辺があるので \(y\) は 2 が書かれたマスであるから \(x-y'\) 間に辺が存在する。
  • \(y\) が invalid なマスである場合 \(x \gets y\) と \(x\) の値を更新して、繰り返しの最初に戻る。
• 繰り返しを break した時点でのマスの列を \(a = (a_0, a_1, \dots, a_{|a|})\) とする。端点が \(a\) に含まれるマッチングの辺を\((a_0,a_1'), (a_0', a_1 ), (a_2,a_3'), (a_2', a_3), \dots\) に張り替えて操作を終了する。
  • 注釈：マス \(x\) に対して頂点 \(x, x'\) はマッチングに高々 1 回しか登場しないことに注目すると \(a_0 = a_{|a|}\) が確認できて、ここからマスの列 \(a\) はグリッドグラフ上のサイクルになるとわかる。グリッドグラフの二部性からサイクルは偶数長であり 2 個ずつに分けることができる。また、\(a\) に含まれる頂点はすべて 2 が書かれたマスなので 隣接するマス \((x, y)\) すべて \(x-y', x'-y\) 間に辺が存在する。

1 回の操作によって、 \(m\) の辺数は変わらないまま \(m\) に含まれる invalid なマスを 1 個以上減らすことができます。よって、\(m\) に invalid なマスが含まれない状態になるまで 高々 \(HW\) 回操作を行えば \(m\) を valid なマッチングにすることができます。

よって、マッチングの辺の本数が 2 の個数と一致していれば必ず valid なマッチングが存在することが証明できました。以上より解法の正当性も証明しました。

• 実装例