首先肯定不能贪心，你如果见缝插针地放坏学生。

前面放的坏学生是会影响后面是否能放坏学生的。

所以一个坏学生相当于“控制”了周围的四格，这一种可选择、不可重复的匹配关系，让我们联系到二分图匹配。

求最多可放的坏学生数量，就相当于求最多不相关可成匹配，也就是最大独立集。

我们先将不可放人的格子，和好学生格子以及其周围四格标记，剩余未标记的格子可以与附近四格的格子连边，表示一种可以匹配的关系。

推荐本 oj 一道题：https://www.oirush.cn/p/P2186

但二分图讲究单向匹配单项寻找，所以将网格分为黑白棋盘格，黑格向白格连边。

最后得出的最大匹配，也就是最小覆盖，而最大独立集 = 总数 - 最小覆盖。

因为左右点各要枚举一次，时间复杂度为 $O(N^2M^2)$，实测常数小飞天速度。

代码：

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

const int N = 90;
bool v[N][N];
char s[N];
int n, m;

vector<int> G[N * N];
int match[N * N], chw[N * N], tsp;

int get_num(int x, int y) {
	return (x - 1) * m + y;
}

bool findmuniu(int x) {
	for (int y : G[x]) {
		if (chw[y] != tsp) {
			chw[y] = tsp;
			if (match[y] == 0 || findmuniu(match[y])) {
				match[y] = x;
				return 1;
			}
		}
	}
	return 0;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	memset(v, 0, sizeof(v));
	int sumo = 0, sumt = 0;
	
	for (int i = 1; i <= n; i ++) {
		cin >> (s + 1);
		for (int j = 1; j <= m; j ++) {
			if (s[j] == '1') {
				v[i][j] = 1;
			}
			else if (s[j] == '2') {
				v[i][j] = 1;
				sumt ++;
				if (i - 1 >= 1 && v[i - 1][j] == 0) {
					v[i - 1][j] = 1;
				}
				if (i + 1 <= n && v[i + 1][j] == 0) {
					v[i + 1][j] = 1;
				}
				if (j - 1 >= 1 && v[i][j - 1] == 0) {
					v[i][j - 1] = 1;
				}
				if (j + 1 <= m && v[i][j + 1] == 0) {
					v[i][j + 1] = 1;
				}
			}
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) if (v[i][j] == 1) {
			sumo ++;
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) if (v[i][j] == 0 && ((i + j) % 2 == 0)) {
			int id = get_num(i, j);
			if (i - 1 >= 1 && v[i - 1][j] == 0) {
				G[id].push_back(get_num(i - 1, j));
			}
			if (i + 1 <= n && v[i + 1][j] == 0) {
				G[id].push_back(get_num(i + 1, j));
			}
			if (j - 1 >= 1 && v[i][j - 1] == 0) {
				G[id].push_back(get_num(i, j - 1));
			}
			if (j + 1 <= m && v[i][j + 1] == 0) {
				G[id].push_back(get_num(i, j + 1));
			}
		}
	}
	
	tsp = 0;
	memset(chw, 0, sizeof(chw));
	memset(match, 0, sizeof(match));
	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) if (v[i][j] == 0 && ((i + j) % 2 == 0)) {
			int id = get_num(i, j);
			tsp = id;
			if (findmuniu(id)) {
				ans ++;
			}
		}
	}
	
	cout << (n * m - sumo - ans + sumt) << "\n";
	
	return 0;
}