C. Portal_C/C++/C#

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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ff first
#define ss second
#define lowbit(x) (x&-x)
#define pf(a) printf("%dn",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 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;
}

C. Portal

C/C++/C#相关栏目本月热门文章