C. Corners（贪心/思维/构造）

题目

题意

给定n*m的01二维矩阵，现可以从01矩阵中选择一个L型的、由3个字符组成的连通块，要求该L型联通块至少包含一个1。并将选中的连通块，字符都变为0。

问，在01矩阵全部变成0之前，最多能用使用多少次L型联通块。

比如4*3的01矩阵

101
111
011
110

它最多可以执行8次

思路

贪心。 如果图中存在一个L型的、包含2个0的联通块，那么我们可以不浪费任何一个1。此时，图中有多少个1，我们就可以应用多少次L型连通块。 因为我们从包含2个0的L型联通块开始，逐个的侵蚀所有的1。最后，地图就全部变成0啦。

如果图中不存在一个L型的、包含2个0的联通块，但存在一个L型的、包含1个0的联通块。那么此时，我们只能牺牲一个1了。即初始选择的L型连通块，会包含2个1。

如果图中不存在0，那么此时我们就只能牺牲2个1了。即初始选择的L型连通块，会包含3个1。

详见代码

代码

#include 
using namespace std;
#define ll long long
const int maxn = 510;
const int mod = 998244353;

int n, m;
char s[maxn][maxn];
int dx[] = {0, 0, 1, -1, -1, -1, 1, 1};
int dy[] = {1, -1, 0, 0, -1, 1, -1, 1};
bool check(int x, int y) {
	if (x = n || y = m) {
		return false;
	}
	return true;
}
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i