Untitled

#include<iostream>
using namespace std;

int T, hang, cot;
int arr[50][50], visit[50][50];
long rs;
int dx_c[6] = {-1, 0, 1, 1, 1, 0};
int dy_c[6] = {0, 1, 1, 0, -1, -1};
int dx_l[6] = {-1, -1, 0, 1, 0, -1};
int dy_l[6] = {0, 1, 1, 0, -1, -1};



void nhap() {
	cin >> cot >> hang;
	for(int i = 0; i < hang; i ++) {
		for(int j = 0; j < cot; j ++) {
			cin >> arr[i][j];
		}
	}
}

void reset() {
	for(int i = 0; i < hang; i ++) {
		for(int j = 0; j < cot; j ++) {
			visit[i][j] = 0;
		}
	}
}

bool cdk(int x, int y) {
	if(x >= 0 && x < hang && y >= 0 && y < cot) return true;
	return false;
}

void dequy(int x, int y, int count, int gg = 0) {
	if(gg == 3) {
		if(count > rs) rs = count;
		return;
	}
	if((y+1)%2) { //le
		for(int j = 0; j < 6; j ++) {
			int xx = x + dx_l[j];
			int yy = y + dy_l[j];
			if(cdk(xx,yy) && visit[xx][yy] == 0) {
				visit[xx][yy] = 1;
				dequy(xx, yy, count + arr[xx][yy], gg+1);
				visit[xx][yy] = 0;
			}
		}
	}
	else {
		for(int j = 0; j < 6; j ++) {
			int xx = x + dx_c[j];
			int yy = y + dy_c[j];
			if(cdk(xx,yy) && visit[xx][yy] == 0) {
				visit[xx][yy] = 1;
				dequy(xx, yy, count + arr[xx][yy], gg+1);
				visit[xx][yy] = 0;
			}
		}
	}
}

int xc1[3] = {0,0,1};
int yc1[3] = {-1,1,0};
int xc2[3] = {-1,1,1};
int yc2[3] = {0,1,-1};
int xl1[3] = {-1,-1,1};
int yl1[3] = {-1,1,0};
int xl2[3] = {-1,0,0};
int yl2[3] = {0,1,-1};
int c1(int x, int y) {
	int count = arr[x][y];
	for(int i = 0; i < 3; i ++) {
		int xx = x + xc1[i];
		int yy = y + yc1[i];
		if(cdk(xx,yy)) count += arr[xx][yy];
		else return 0;
	}
	return count;
}

int c2(int x, int y) {
	int count = arr[x][y];
	for(int i = 0; i < 3; i ++) {
		int xx = x + xc2[i];
		int yy = y + yc2[i];
		if(cdk(xx,yy)) count += arr[xx][yy];
		else return 0;
	}
	return count;
}

int l1(int x, int y) {
	int count = arr[x][y];
	for(int i = 0; i < 3; i ++) {
		int xx = x + xl1[i];
		int yy = y + yl1[i];
		if(cdk(xx,yy)) count += arr[xx][yy];
		else return 0;
	}
	return count;
}

int l2(int x, int y) {
	int count = arr[x][y];
	for(int i = 0; i < 3; i ++) {
		int xx = x + xl2[i];
		int yy = y + yl2[i];
		if(cdk(xx,yy)) count += arr[xx][yy];
		else return 0;
	}
	return count;
}

void checkY() {
	int count = 0;
	for(int i = 0; i < hang; i ++) {
		for(int j = 0; j < cot; j ++) {
			if((j+1)%2) { //le
				if(l1(i,j) > l2(i,j)) count = l1(i,j);
				else count = l2(i,j);
			}
			else {
				if(c1(i,j) > c2(i,j)) count = c1(i,j);
				else count = c2(i,j);
			}
			if(count > rs) rs = count;
		}
	}
}

int main() {
//	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++) {
		nhap();
		rs = 0;
		for(int i = 0; i < hang; i ++) {
			for(int j = 0; j < cot; j ++) {
				reset();
				visit[i][j] = 1;
				dequy(i,j, arr[i][j]);
			}
		}
		checkY();
		cout << "Case #" << tc << endl << rs*rs << endl;
	}
	return 0;
}