3218070_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define inf 2100000000

int ans;

void rotate(int pp[101][101],int n,int m)
{
	int i, j;
	int tmp[101][101];

	memcpy(tmp,pp,sizeof(tmp));
	memset(pp,0,sizeof(pp));
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < m; j++)
		{
			pp[j][i] = tmp[i][j];
		}
	}
}

void upturn(int pp[101][101],int n,int m)
{
	int i, j;
	int tmp[101][101];

	memcpy(tmp,pp,sizeof(tmp));
	for(i = n-1; i >= 0; i--)
	{
		for(j = 0; j < m; j++)
		{
			pp[n-i-1][j] = tmp[i][j];
		}
	}
}

void leftturn(int pp[101][101],int n,int m)
{
	int i, j;
	int tmp[101][101];

	memcpy(tmp,pp,sizeof(tmp));
	for(i = 0; i < n; i++)
	{
		for(j = m-1; j >= 0; j--)
		{
			pp[i][m-1-j] = tmp[i][j];
		}
	}
}

void save(int t)
{
	if(ans==inf||t>ans)
		ans = t;
}

void solve(int pp[101][101],int n,int m,int b)
{
	int tmp[101][101];
	int i, j;
	int t, tt;

	if(n >= 3 && m >= 4)
	{
		for(i = 1; i < n-1; i++)
		{
			for(j = 0; j <= m-4; j++)
			{
				tt = pp[i][j]+pp[i][j+1]+pp[i][j+2]+pp[i][j+3];
				t = tt+pp[i-1][j]+pp[i+1][j];
				save(t);
				t = tt+pp[i-1][j]+pp[i+1][j+1];
				save(t);
				t = tt+pp[i-1][j]+pp[i+1][j+2];
				save(t);
				t = tt+pp[i-1][j]+pp[i+1][j+3];
				save(t);
				t = tt+pp[i-1][j+1]+pp[i+1][j+2];
				save(t);
				t = tt+pp[i-1][j+1]+pp[i+1][j+1];
				save(t);

				tt = tt-pp[i][j]+pp[i-1][j]+pp[i-1][j+1];
				t = tt+pp[i+1][j+1];
				save(t);
				t = tt+pp[i+1][j+2];
				save(t);
				t = tt+pp[i+1][j+3];
				save(t);

				tt = tt-pp[i][j+3];
				t = tt+pp[i+1][j+2]+pp[i+1][j+3];
				save(t);
			}
		}
	}
	if(m >= 5)
	{
		for(i = 0; i < n-1; i++)
		{
			for(j = 0; j <= m-5; j++)
			{
				t = pp[i][j]+pp[i][j+1]+pp[i][j+2]+pp[i+1][j+2]+pp[i+1][j+3]+pp[i+1][j+4];
				save(t);
			}
		}
	}
	if(b)
	{
		memcpy(tmp,pp,sizeof(tmp));
		upturn(tmp,n,m);
		solve(tmp,n,m,0);
		memcpy(tmp,pp,sizeof(tmp));
		leftturn(tmp,n,m);
		solve(tmp,n,m,0);
	}
}

void output(int a[][101],int n,int m)
{
	printf("\n");
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int main()
{
	int n, m;
	int i, j;
	int tn, tm;
	int pp[101][101], tmp[101][101];

	scanf("%d%d",&n,&m);
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < m; j++)
		{
			scanf("%d",&pp[i][j]);
		}
	}
	ans = inf;
	memcpy(tmp,pp,sizeof(pp));
	tn = n;tm = m;
	for(i = 0; i < 4; i++)
	{
		solve(tmp,tn,tm,1);
		rotate(tmp,tn,tm);
		swap(tn,tm);
		//output(tmp,n,m);
	}
	memcpy(tmp,pp,sizeof(pp));
	tn = n;tm = m;
	upturn(tmp,tn,tm);
	solve(tmp,tn,tm,1);
	memcpy(tmp,pp,sizeof(pp));
	tn = n;tm = m;
	leftturn(tmp,tn,tm);
	solve(tmp,tn,tm,1);
	printf("%d\n",ans);
	return 0;
}