CF 1580 A

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll __int64
#define speed(x) ios::sync_with_stdio(false), cin.tie(x), cout.tie(x)
#define bug(x) cout << #x << " == " << x << '\n'
const ll int MAX_N = 1e6+ 5;
#define ls p * 2
#define rs p * 2 + 1
#define md (l + r) / 2
using namespace std;
ll mod=1e9+7;
const int maxn=3e3+10;
int a[maxn][maxn]= {0};
char mp[maxn][maxn];
int sum[maxn][maxn]= {0};
inline int getsum(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];
}
inline cl(int x1,int y1,int x2,int y2)
{
    int ans=0;
    ans+=getsum(x1+1,y1+1,x2-1,y2-1);
    ///门内所有的1要改成0
    ans += ( 2*(x2-x1+y2-y1)-(getsum(x1,y1,x2,y2)-getsum(x1+1,y1+1,x2-1,y2-1)) );
    ///门的边框需要是1
    if(mp[x1][y1]=='0')
    {
        ans--;///门框四个角不需要改1
    }
    if(mp[x2][y1]=='0')
    {
        ans--;///门框四个角不需要改1
    }
    if(mp[x1][y2]=='0')
    {
        ans--;///门框四个角不需要改1
    }
    if(mp[x2][y2]=='0')
    {
        ans--;///门框四个角不需要改1
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%s",mp[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];
                if(mp[i][j]=='1')
                {
                    sum[i][j]++;
                }
            }
        }
        int ans=cl(1,1,5,4);
        for(int i=1; i<=n; i++)
        {
            for(int ii =i+4; ii<=n; ii++)
            {
                int j=1;
                for(int jj=4; jj<=m; jj++)///枚举每一个宽度即可
                {
                    int tmp;
                    if ((tmp = cl(i, j, ii, jj)) < ans) // 这样赋值，一定要将括号括号
                    {
                        ans = tmp;
                    }
                    while (jj - j > 3 && (tmp = cl(i, j + 1, ii, jj)) < ans)
                    {
                        j++;
                        ans = tmp;
                    }
                    if ((tmp = cl(i, jj - 3, ii, jj)) < ans)
                    {
                        j = jj - 3;
                        ans = tmp;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
}