好些日子没写博客了，最近这些日子有在调整状态。后边准备大量刷题了

好的言归正传，说一下这道题是一个老坑了，今天终于填上了。先放一下题目链接：https://codeforces.com/contest/1581/problem/C，这道题大致意思就是，现在有一个n*m大小的点阵，1代表黑曜石，0代表空，现在要选出一个子矩阵经过打碎黑曜石或者填补黑曜石，来形成一个大小至少为4*5的地狱传送门，（地狱传送门是有一个外边框由黑曜石构成，中间是空的，不包括四个边角）。当时写这道题想到的就是二维前缀和，枚举左上角和右下角，这明显时间复杂度为O(n²*m²)，时间复杂度爆表的好吧。看了下别人的submit，突然发现我有些性质没用上。我个人认为这道题有点动态规划内味了。下面说一下解决方案

我们先去枚举列区间，分别是l和r，然后枚举行，但注意我们枚举行只去枚举一行，而非像列一样的去枚举区间。对于每一行去找它可去选择的另一行。如果说设当前行为k，它可选择的另一行i(i<k)，就可以是从1到k-4，但这样去枚举的话又是最暴力的复杂度了。所以转变思路。当k加一的时候，i可选择范围也会加一，最后我们只需对比上一个k取最优解时的i和选第k-4行进行对比，哪个花费少就选取哪一个。证明的话，简单说一下i和k-4之间肯定无更优解（开区间），因为上一个k选择的是i，那当前的k来说在此区间内也不可能会有比i更好的解。所以剩下的其实就是i和k-4这个新生的选择之间的较量。我的语言表述能力有限，还是贴一份代码去理解吧

#include <bits/stdc++.h>
using namespace std;
char s[500][500];
int a[500][500],b[500][500],sum[500][500];
int get1(int x1,int y1,int x2,int y2){
	return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int get0(int x1,int y1,int x2,int y2){
	return (x2-x1+1)*(y2-y1+1)-(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);
}
int getSum(int x1,int y1,int x2,int y2){
	int res=0;
	res+=get1(x1+1,y1+1,x2-1,y2-1);
	//cout<<res<<endl;
	res+=get0(x1+1,y1,x2-1,y1);
	//cout<<res<<endl;
	res+=get0(x1+1,y2,x2-1,y2);//cout<<res<<endl;
	res+=get0(x1,y1+1,x1,y2-1);//cout<<res<<endl;
	res+=get0(x2,y1+1,x2,y2-1);
	//cout<<res<<endl;
	return res;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>(s[i]+1);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]=='1');
			}
		}
		int ans=2147483647;
		for(int l=1;l<=m;l++){
			for(int r=l+3;r<=m;r++){
				for(int k=5,now=1;k<=n;k++){
					int nxt=k-4;
					int v1=getSum(now,l,k,r);
					int v2=getSum(nxt,l,k,r);
					if(v1>v2){
						now=nxt;
						v1=v2;
					}
					ans=min(ans,v1);
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}