【简解】宫廷守卫

【题目大意】

在网格图中放象棋里的车，只能放在'0'的空地上，'2'可阻断。要使放置的车两两不能相互攻击，求最大安置数及其方案。

传送门。

【分析】

二分图最大匹配问题。

思考如何建图。

先简化问题，如果没有'2'可阻断这个条件的话，那么就应该对所有空地'0'的第i行连向第j列，然后跑最大匹配。

当有了'2'这个条件之后，我们可以发现，在同一行中，若两块空地中间有'2'，那么它们都可以被选，类似地，对于竖列也是同样的道理，那么我们就可以把每个空地向右走的第一个'2'连向向下走的第一个'2'，然后就可以开心地跑二分图最大匹配了。

【Code】

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int P = 19260817;
const int N = 200 + 5;
inline int read(){
    int f = 1, x = 0; char ch;
    do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0' || ch > '9');
    do {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
    return f * x;
}
inline void hand_in() {
    freopen("guard.in", "r", stdin);
    freopen("guard.out", "w", stdout);
}
int m, n, mp[N][N];
struct Sakura {
    int to, nxt;
}sak[400005]; int head[400005], cnt;
inline void add(int x, int y) {
    ++cnt;
    sak[cnt].to = y, sak[cnt].nxt = head[x], head[x] = cnt;
}
inline int calc(int x, int y) {
    return (x - 1) * (m + 1) + y;
}
int match[400005], vis[400005], ans;
inline bool dfs(int u) {
    for (int i = head[u];i;i = sak[i].nxt) {
        int v = sak[i].to;
        if (!vis[v]) {
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

inline pair <int, int> dis(int t) {
    int x = (t - 1) / (m + 1) + 1;
    int y = t - (x - 1) * (m + 1);
    return make_pair(x, y);
}

int main(){
//  hand_in();
    n = read(), m = read();
    for (int i = 1;i <= n; ++i) {
        for (int j = 1;j <= m; ++j) {
            mp[i][j] = read();
        }
    }
    for (int i = 0;i <= n + 1; ++i) mp[i][0] = mp[i][m + 1] = 2;
    for (int i = 0;i <= m + 1; ++i) mp[0][i] = mp[n + 1][i] = 2;

    for (int i = 1, x, y;i <= n; ++i) {
        for (int j = 1;j <= m; ++j) {
            if (!mp[i][j]) {
                x = i + 1, y = j + 1;
                while (mp[i][y] != 2) y ++;
                while (mp[x][j] != 2) x ++;
                add(calc(i, y), calc(x, j));
            }
        }
    }

    for (int i = 1;i <= n; ++i) {
        for (int j = 1;j <= m; ++j) {
            if (mp[i][j + 1] == 2) {
                memset(vis, 0, sizeof vis);
                if (dfs(calc(i, j + 1))) ++ans;
            }
        }
    }

    printf("%d\n", ans);

    for (int i = 1, t;i <= n; ++i) {
        for (int j = 1;j <= m; ++j) {
            t = calc(i + 1, j);
            if (match[t]) {
                printf("%d %d\n", dis(match[t]).first, j);
            }
        }
    }
    return 0;
}