ongnausol

 avatar
quoc14
c_cpp
5 months ago
2.1 kB
0
Indexable
caidat
#include <iostream>

using namespace std;

int n,m;
int dx[2][6];
int dy[2][6];


int dxc[6] = {-1, 0, 1 , 1, 1, 0};
int dyc[6] = {0, -1, -1, 0, 1, 1};

int dxl[6] = {-1, -1, 0, 1, 0, -1};
int dyl[6] = {0, -1, -1, 0, 1, 1};

int map[100][100];
int kt[100][100];
long long maxans = 0;

int inside(int uu, int vv)
{
	if (uu <=0 || uu >= n+1) return 0;
	if (vv <=0 || vv >= m+1) return 0;
	return 1;
}

long long calc(int i, int j)
{
	//vong tron xung quanh 2 truong hop
	int mod = j%2;
	long long sum1 = map[i][j];
	long long sum2 = map[i][j];
	for (int k = 0; k<=4; k+=2)
	{
		int uu = i + dx[mod][k];
		int vv = j + dy[mod][k];
		if (inside(uu,vv))
		{
			sum1 += map[uu][vv];
		} 

	    uu = i + dx[mod][k+1];
	    vv = j + dy[mod][k+1];
		if (inside(uu,vv))
		{
			sum2 += map[uu][vv];
		} 
	}
	sum1 *= sum1;
	sum2 *= sum2;

	return sum1 > sum2 ? sum1 : sum2;
}

void DFS(int index, int i, int j, int cost)
{
	int mod = (j % 2);
	for (int k = 0; k <6; k++)
	{
		 int uu = i + dx[mod][k];
	     int vv = j + dy[mod][k];
		 if (inside(uu,vv) && kt[uu][vv]==0)
		 {
			 kt[uu][vv] = 1;
			 long long tmpcost = cost + map[uu][vv];
			 if (index == 3)
			 {
				 tmpcost*=tmpcost;
				 if (tmpcost > maxans) maxans = tmpcost;
			 } else if (index < 3)
			 {
				 DFS(index + 1, uu, vv, tmpcost);
			 }
			 kt[uu][vv] = 0;
		 }
	}
}

void init()
{
	for (int i = 0; i < 6; i++)
	{
		dx[0][i] = dxc[i];
		dx[1][i] = dxl[i];

		dy[0][i] = dyc[i];
		dy[1][i] = dyl[i];
	}
}
int main()
{
	init();
	//freopen("input.txt","r",stdin);
	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{
		cin >> m >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				cin >> map[i][j];

		maxans = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <=m; j++)
			{
				long long tmp = calc(i,j);
				if (tmp > maxans) maxans = tmp;
				kt[i][j] = 1;
				DFS(1,i,j,map[i][j]);
				kt[i][j] = 0;
			}

			cout <<"Case #"<<tc<< endl << maxans << endl;

	}

	return 0;
}
Leave a Comment