奇妙 ios&&90pts金石候任
查看原帖
奇妙 ios&&90pts金石候任
982513
EternalHeart1314楼主2025/1/9 15:54

交了 N 发,把 ios 删了就过了???!!!

#include <bits/stdc++.h>
using namespace std;

const int N = 233, dx[] = {-1, -2, 1, 2, -1, -2, 1, 2}, dy[] = {-2, -1, -2, -1, 2, 1, 2, 1};
int n, ans, a[N][N], cp[N * N], rv[N * N];
vector<int> e[N * N];

inline int get(int x, int y) { return (x - 1) * (n + 1) + y; }
inline int dfs(int u, const int RV) {
	if (rv[u] == RV) return 0;
	rv[u] = RV;
	for (auto v : e[u]) if (!cp[v] || dfs(cp[v], RV))
		return cp[v] = u, 1;
	return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);//删了这两行
    cin >> n; char c;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) cin >> c, ans += a[i][j] = c ^ 49;
        getchar();
    }
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
        if (a[i][j]) for (int k = 0, x, y; k < 8; ++k) {
            x = i + dx[k], y = j + dy[k];
            if (x < 1 || x > n || y < 1 || y > n || !a[x][y]) continue;
            if (i + j & 1) e[get(i, j)].push_back(get(x, y));
        }
    }
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
        memset(rv, 0, sizeof rv);
        ans -= dfs(get(i, j), get(i, j));
    }
    return cout << ans, 0;
}
2025/1/9 15:54
加载中...