C. Portal-蒲公英云

C. Portal

https://codeforces.com/contest/1581/problem/C

暴力n^4 方，当枚举最后一列之前，判断是否大于16，大于就剪枝，16是最坏情况下的修改数

为什么16是最坏情况呢？
想想，5行4列，四个边角不需要改变，那就是4*5 - 4 = 16；

先枚举行，再枚举列，枚举最后一列的时候，之前的矩形需要修改的数量已经是确定好了，如果已经确定好的数都大于最坏情况，直接break;

然后就是一些预处理啦，保证每次在O(1)时间内算出当前方案需要修改的数。

// Problem: C. Portal
// Contest: Codeforces - Codeforces Round #745 (Div. 2)
// URL: https://codeforces.ml/contest/1581/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
using namespace std;
#define ff first
#define ss second
#define lowbit(x) (x&-x)
#define pf(a) printf("%d\n",a)
#define mem(x,y) memset(x,y,sizeof(x))
#define dbg(x) cout << #x << " = " << x << endl
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define fep(i,a,b) for(int i=b; i>=a; --i)
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int N=500;
int n, m;
int a[N][N];
int x[N][N], y[N][N], s[N][N];
void solve()
{ 
    mem(a,0);
    mem(x,0); // 计算某行的某个区间内0的个数
    mem(y,0); // 计算某列的某个区间内0的个数
    mem(s,0);
    cin >> n >> m;
    rep(i,1,n)
    { 
        string str; cin >> str;
        str = " " + str;
        rep(j,1,m)
        { 
            a[i][j] = str[j] - '0';
            x[i][j] = a[i][j] + x[i][j-1];
            if(a[i][j]==1)
            { 
                s[i][j]=1+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            }
            else s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    for(int i = 1; i <= m; i++)
    { 
        for(int j = 1; j<= n; j++)
        { 
            y[j][i] = y[j-1][i] + a[j][i];
        }
    }
    int ans = 16;
    for(int i=1;i <= n; i++)
    { 
        for(int j=i+4;j<=n;j++)
        { 
            for(int k=1;k<=m;k++)
            { 
                for(int z=k+3;z<=m;z++)
                { 
                    int all = 0;
                    int x2 = j-1, y2 = z-1, x1 = i+1, y1 = k+1;
                    int c1 = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
                    // 中间需要改成0的个数
                    int c2 = z - k - 1 - (x[i][z-1]-x[i][k]); // 0的个数
                    //上
                    int c3 = z - k - 1 - (x[j][z-1]-x[j][k]);
                    //下
                    int c4 = j - i - 1 - (y[j-1][k]-y[i][k]);
                    //左
                    int sum = c1 + c2 + c3 + c4;
                    if(sum > 16) break; // 如果这
                    int c5 = j - i - 1 - (y[j-1][z]-y[i][z]);
                    //右
                    sum += c5;
                    ans = min(ans, sum);
                }
            }
        }
    }
    cout << ans << endl;
}
int main()
{ 
    int Case;scanf("%d", &Case);
    while(Case--)
        solve();
    return 0;
}