Untitled

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int n, m;
int a[16][16];
int dx[2][6] = {{-1, 1, 1, 0, 1, 0}, {-1, 0, 0, -1, 1, -1}};
int dy[2][6] = {{0, 1, -1, 1, 0, -1}, {0, 1, -1, 1, 0, -1}};
int ans = 0;
void calcAdj(int x, int y) {
	int sum1 = a[x][y], sum2 = a[x][y];
	for(int i = 0; i < 3; i++) {
		int x1 = x + dx[y%2][i], y1 = y + dy[y%2][i];
		int x2 = x + dx[y%2][3 + i], y2 = y + dy[y%2][3 + i];
		//cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << sum1 << " " << sum2 << endl;;
		if(x1 > 0 && x1 <= n && y1 > 0 && y1 <= m) {
			//cout << a[x1][y1] << " ";
			sum1 += a[x1][y1];
		}
		if(x2 > 0 && x2 <= n && y2 > 0 && y2 <= m) {
			//cout << a[x2][y2] << " ";
			sum2 += a[x2][y2];
		}
		//cout << endl;
	}
	int sumM = max(sum1, sum2);
	//cout << sumM << " " << ans << endl;
	ans = max(ans, sumM);
}
void dfs(int cnt, int x, int y, int sum) {
	if(cnt == 4) {
		//if(sum > ans) cout << sum << endl;
		ans = max(ans, sum);
		return;
	}
	int curr = a[x][y];
	a[x][y] = -1;
	for(int i = 0; i < 6; i++) {
		int x1 = x + dx[y%2][i];
		int y1 = y + dy[y%2][i];
		if(x1 > 0 && x1 <= n && y1 > 0 && y1 <= m && a[x1][y1] != -1) {
			//cout << x1 << " " << y1 << " " << sum << " " << a[x1][y1] << " = " << sum + a[x1][y1] <<  endl;
			
			dfs(cnt + 1, x1, y1, sum + a[x1][y1]);
		}
	}
	a[x][y] = curr;
}
int main(int argc, char** argv) {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int T = 10; 
	cin >> T;
	for(int tc = 1; tc <= T; tc++) {
		ans = 0;
		cin >> m >> n;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				//cout << a[i][j] << " " << i << ":" << j << "\n";
				calcAdj(i, j);
				dfs(1, i, j, a[i][j]);

			}
			//cout << endl;
		}
		cout << "Case #" << tc << "\n" << 1ll * ans * ans << endl;
		//cout << a[14][15] << endl;
		
	}
	return 0;
}