This problem can be formalized as a matching problem as follows.

Define a vertex corresponding to each square. Add an edge between two vertices if corresponding squares are adjacent and neither has 1. Is there a matching on this graph such that every vertex with 2 is matched?

Graph corresponding to Sample Input 1

Since this graph is bipartite, it can be boiled down to the following flow problem:

Let \(A\) and \(B\) be the vertex sets of the bipartite graph defined above. Direct each edge from \(A\) to \(B\). Add vertices \(S\) and \(T\), and add an edge from \(S\) to each vertex of \(A\), and from each vertex of \(B\) to \(T\). Let the capacity of every edge \(1\). Is there a flow from \(S\) to \(T\) such that, for all vertices with 2, the flow of the edge connecting that vertex and \(S\) or \(T\) is \(1\)?

Graph corresponding to Sample Input 1

This is nothing but a (maximum) flow problem with minimum capacities, which can be solved with an algorithm solving max-flow problem.

Since the graph to find the flow has \(O(HW)\) edges, all of which have a capacity of \(1\), so the problem has been solved in a total of \(O((HW)^{1.5})\) time with Dinic’s algorithm.

Writer’s solution (C++)

Maximum flow problem with minimum capacities

We describe how to find the maximum flow from \(S\) to \(T\) when the edges also constrain the minimum bound of the flow amount (edges have “minimum capacities”). It can be boiled down to an ordinary max-flow problem.
Consider an edge from \(u\) to \(v\) whose capacity is \(R\) and minimum capacity is \(L\). To deal with the minimum capacity, create a new vertex \(S'\) to \(T'\), remove the original edge, and add edges with the following capacities:

Add such edges for all edges with the minimum capacities. On the resulting graph, accumulate maximum flow in the following order:

• from \(S'\) to \(T'\)
• from \(S'\) to \(T\)
• from \(S\) to \(T'\)
• from \(S\) to \(T\).

An \(S-T\) flow that satisfies the minimum capacities exists if and only if, for all outgoing edges from \(S'\) and incoming edges to \(T'\), the flow and capacity are equal. (This can be understood by corresponding the flows from \(S'\) and \(T'\) to the original edges.)

Alternatively, if you just want to know the existence of a flow satisfying the minimum capacities, one can add an edge from \(T \) to \(S\) with infinite capacity and consider the flow from \(S'\) to \(T'\) once, instead of accumulating flows four times.

Reference:

• Maximum flow with minimum capacities (Article in Japanese by snuke)
  
• 『プログラミングコンテストチャレンジブック　第2版』 (Programming Contest Challenge Book, 2nd Edition), page 193