Solution to AT_abc285_g Tatami

Statement

请用若干个 \(1 \times 1\) 和 \(1 \times 2\) 的瓷砖（可以旋转）不重叠地完全覆盖 \(H \times W\) 的长方形网格。第 \(i\) 行第 \(j\) 列的网格有字符 \(c_{i,j}\)，含义如下：

• 1：该网格只能用 \(1 \times 1\) 的瓷砖覆盖。
• 2：该网格只能用 \(1 \times 2\) 的瓷砖覆盖。
• ?：该网格无特殊限制。

如果存在方案可以满足上述条件，输出 Yes，否则输出 No。

\(1 \leq H,W \leq 300\)。

Solution

每个格子只能被覆盖一次，考虑拆点网络流。

Conclusion

• 设源点 \(S\)，汇点 \(T\)。从 \(S\) 向入点连边，从出点向 \(T\) 连边。
• 如果某个方格上是 \(1\)，将它代表的点的入点向出点连边。
• 如果是 \(2\)，从其入点向它四连通的 \(2\) 或 \(?\) 方格的出点连边。
• 如果是 \(?\)，当作其为 \(1\) 和 \(2\) 处理。
• 所连的边容量均为 \(1\)。

求解最大流 \(f\)，若 \(f = nm\) 则有解；反之无解。

Proof

对于 \(1\) 类方格（方格上写着 \(1\)，下同），求解最大流时必然有 \(1\) 的贡献。

对于一条由 \(2\) 类方格组成的链，长度为 \(n\)，显然地，求解最大流必然有 \(\lfloor\frac{n}{2}\rfloor\) 的贡献。

观察到如果不是链，总可以将叶子位置的方格换到别的叶子后面去，从而转化成一条链的情况。

Code

#include <bits/stdc++.h>

struct Edge {
	int to, nxt, cap, flow;
	Edge() = default;
	Edge(int to, int nxt, int cap, int flow) : to(to), nxt(nxt), cap(cap), flow(flow) {}
};

class Graph {
public:
	int n, m;
	std::vector<Edge> ed;
	std::vector<int> head;
	int cnt;
	void add_edge(int u, int v) { ed[++cnt].to = v, ed[cnt].nxt = head[u], head[u] = cnt; }
	Graph(int n, int m) : n(n), m(m), ed(m), head(n + 1, -1), cnt(-1) {}
};

class NetworkFlow : public Graph {
private:
	const int INF = 0x3f3f3f3f;
	std::vector<int> dep;

	bool bfs(int s, int t) {
		std::queue<int> q;
		while (q.size()) q.pop();
		dep.assign(n + 1, 0);
		dep[s] = 1;
		q.push(s);
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (int i = head[x]; ~i; i = ed[i].nxt) {
				if ((!dep[ed[i].to]) && (ed[i].cap > ed[i].flow)) {
					dep[ed[i].to] = dep[x] + 1;
					q.push(ed[i].to);
				}
			}
		}
		return dep[t] > 0;
	}

	int dfs(const int x, const int t, int flow) {
		if (x == t || (!flow)) return flow;
		int ret = 0;
		for (int& i = cur[x]; ~i; i = ed[i].nxt) {
			int d;
			if ((dep[ed[i].to] == dep[x] + 1) &&
				(d = dfs(ed[i].to, t, std::min(flow - ret, ed[i].cap - ed[i].flow)))) {
				ret += d;
				ed[i].flow += d;
				ed[i ^ 1].flow -= d;
				if (ret == flow) return ret;
			}
		}
		return ret;
	}

public:
	int s, t;
	std::vector<int> cur;

	NetworkFlow(int n, int m) : Graph(n + 3, m), dep(n + 3), s(n + 1), t(n + 2), cur(n + 3) {}

	void add_edge(int u, int v, int w) {
		ed[++cnt].to = v, ed[cnt].nxt = head[u], head[u] = cnt;
		ed[cnt].cap = w, ed[cnt].flow = 0;
	}

	int dinic() {
		int max_flow = 0;
		while (bfs(s, t)) {
			cur = head;
			max_flow += dfs(s, t, INF);
		}
		return max_flow;
	}
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

	int n, m;
	std::cin >> n >> m;
	NetworkFlow G(n * m * 2, n * m * 14);
	std::vector<std::vector<int>> a(n + 2, std::vector<int>(m + 2));

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			char x;
			std::cin >> x;
			if (x == '?')
				a[i][j] = 0;
			else if (x == '1')
				a[i][j] = 1;
			else
				a[i][j] = 2;
		}
	}

	auto valid = [&a, n, m](int x, int y) {
		return x >= 1 && x <= n && y >= 1 && y <= m && (a[x][y] == 2 || a[x][y] == 0);
	};
	auto convert = [n, m](int x, int y, bool f) { return (x - 1) * m + y + f * n * m; };

	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, -1, 1};

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			G.add_edge(G.s, convert(i, j, 0), 1);
			G.add_edge(convert(i, j, 0), G.s, 0);
			G.add_edge(convert(i, j, 1), G.t, 1);
			G.add_edge(G.t, convert(i, j, 1), 0);
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (a[i][j] == 1 || a[i][j] == 0) {
				G.add_edge(convert(i, j, 0), convert(i, j, 1), 1);
				G.add_edge(convert(i, j, 1), convert(i, j, 0), 0);
			}
			if (a[i][j] == 2 || a[i][j] == 0) {
				for (int k = 0; k < 4; ++k) {
					if (!valid(i + dx[k], j + dy[k])) continue;
					G.add_edge(convert(i, j, 0), convert(i + dx[k], j + dy[k], 1), 1);
					G.add_edge(convert(i + dx[k], j + dy[k], 1), convert(i, j, 0), 0);
				}
			}
		}
	}

	int max_flow = G.dinic();
	std::cerr << max_flow << '\n';
	if (max_flow == n * m)
		std::cout << "Yes" << '\n';
	else
		std::cout << "No" << '\n';
	return 0;
}