1581C - Portal - CodeForces Solution

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using ll = long long;
const int mod = 1e9+7;
const int N = 405;
int dp[N][N];
char s1[N][N];
void suan(int l1,int r1,int x)
{
	dp[l1][r1]=x;
	dp[l1][r1]+=dp[l1-1][r1]+dp[l1][r1-1]-dp[l1-1][r1-1];
}
int he (int l1,int r1,int l2,int r2)
{
	int res = 0;
	res=dp[l2][r2]-dp[l1-1][r2]-dp[l2][r1-1]+dp[l1-1][r1-1];
	return res;
}
int main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			scanf("%s",s1[i]+1);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
		{
			int x = s1[i][j]-'0';
			suan(i,j,x);
		}
		int ans = 1e9; 
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				for(int k=i+4;k<=n;k++)
					for(int u=j+3;u<=m;u++)
		{
			int sum = -he(i+1,j,k-1,j)-he(i,j+1,i,u-1)+he(i+1,j+1,k-1,u-1)-he(i+1,u,k-1,u)-he(k,j+1,k,u-1);
			sum+=(k-i-1)*2+(u-j-1)*2;
			int tem = sum + he(i+1,u,k-1,u) - (k - i - 1);
			if(tem>=ans)break;
			ans=min(ans,sum);
		}
		cout<<ans<<endl;
	}
}