【题解】CF1720C

题意简述

给你一个 01 矩阵，每一次你可以在这个矩阵中找到一个 $L$ 型，将它全部变成 0。$L$ 型的定义是在一个 $2\times2$ 矩阵中，除开一个角之外的图形，其中必须包含至少一个 1。

现在需要你找到将整个矩阵变成 1 的最大操作数。

题目分析

由于 L 型是在一个 2$\times$2 的矩阵中，所以我们不妨从这里开始分析。

1. 如果矩阵没有 0

1 1

1 1

这种情况会有 4 个 1。

显然，第一次操作至少会让三个 1 变成 0，然后转到情况 4，这时候最大操作数是 2。

此时，操作数 = 1 的个数 -2。

2. 如果矩阵只有一个 0

0 1

1 1

其中的一种情况是上面这样的，这时候会有 3 个 1。

同样的，第一次操作至少会让两个 1 变成 0，然后转到情况 4，这时候最大的操作数是 2。

此时，操作数 = 1 的个数 -1。

3. 如果矩阵只有两个 0

0 1 | 0 0

1 0 | 1 1

其中有两种情况如上图，这时候会有 2 个 1。

这时候第一次操作可以只改变一个 1，接着转到情况 4，最大的操作数是 2。

此时，操作数 = 1 的个数。

4. 如果矩阵只有三个 0

0 0

0 1

其中一种情况如上，这时候有 1 个 1.

这时候只能改变一个 1,操作数也就是 1。同时显然，矩阵中没有 1 是操作数是 0，这里便不做分类讨论。

此时，操作数 = 1 的个数。

根据上面的分析，我们可以大胆猜想，设 1 的个数为 x，0 的个数为 y，操作数为 ans，则在 2$\times$2 矩阵中：

$\begin{cases}
ans &= x-2 &(y=0) \\
ans &= x-1 &(y=1) \\
ans &=x &(y\ge2)
\end{cases}$

我们尝试将结论推广到普通矩阵中。

没有 0 的情况显然和之前一样。

而这时候就不是只有 1 个 0 的情况，而是在一个 2$\times$2 矩阵中只有 1 个 0。

同样，至少有 2 个 0 的情况也需要转移到在 2$\times$2 矩阵中至少有 2 个 0。

这样我们只要求出 1 的个数并且判断在 2$\times$2 矩阵中有没有至少两个 0 即可。

为什么这种思路是正确的？

一个任意的 n$\times$m 矩阵（$n,m\ge2$）,都会包含若干个 2$\times$2 的矩阵，即使矩阵可能会重叠。

如果其中有一个矩阵有大于 1 个的 0，就可以从这里开始操作，扩展到每个 2$\times$2 矩阵都有大于 1 个的 0，情况简化成最开始分析中的第三种情况。否则就只能按照第二种情况来扩展。

#include<bits/stdc++.h>

using namespace std;

const int N=5e2+5;

int n,m;

int a[N][N];

signed main(){

	ios::sync_with_stdio(false);

	int t;

	cin>>t;

	while(t--){

		cin>>n>>m;

		int suma=0,sumb=0;//suma是0的个数，sumb是1的个数。其实只记录其中的一个也可以

		bool f=false;

		for(int i=1;i<=n;i++){

			string s;

			cin>>s;

			for(int j=0;j<m;j++) a[i][j+1]=s[j]-'0';

		}

		for(int i=1;i<=n;i++){

			for(int j=1;j<=m;j++){

				if(a[i][j]==0){

					suma++;

					//下面判断2*2矩阵中有两个0的情况，注意判断数组越界，用循环也可以

					if((i+1<=n&&a[i+1][j]==0)||(i-1>=1&&a[i-1][j]==0)||(j-1>=1&&a[i][j-1]==0)||(j+1<=m&&a[i][j+1]==0)) f=true;//两个0是相邻的

					else if((i+1<=n&&j+1<=m&&a[i+1][j+1]==0)||(i-1>=1&&j-1>=1&&a[i-1][j-1]==0)||(i+1<=n&&j-1>=1&&a[i+1][j-1]==0)||(i-1>=1&&j+1<=m&&a[i-1][j+1]==0)) f=true;//两个0称对角

				}

				else sumb++;

			}

		}

		if(suma==0) cout<<sumb-2<<"\n";//都是1

		else if(sumb==0) cout<<"0\n";//都是0

		else if(f==false) cout<<sumb-1<<"\n";//所有2*2矩阵中都只有一个0

		else cout<<sumb<<"\n";//任意2*2矩阵中有至少两个0

	}

	return 0;

}

巴特西