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;
}