Untitled

#include <iostream>
using namespace std;
int n, m;
int arr[100][100];
int mt[20][20];
int dR[6] = {-1, -2, -1, 1, 2, 1};
int dC[6] = {-1, 0, 1, 1, 0, -1};
int visited[100][100];
int Max;

void BackTrack(int i, int j, int dem, int sum){

	if(dem == 4){
		Max = max(Max, sum);
		return;
	}

	for(int k=0; k<6; k++){
		int x = i + dR[k];
		int y = j + dC[k];

		if(x>=1 && x<=n && y>=1 && y<=m && visited[x][y] == 0 && arr[x][y] != 0){
			visited[x][y] = 1;

			BackTrack(x, y, dem + 1, sum + arr[x][y]);

			visited[x][y] = 0;
		}

	}

}

void check(int i, int j){

	int count1 = 0, count2 = 0;
	int temp1 = -1, temp2 = -1;
	int sum1 = arr[i][j], sum2 = arr[i][j];

	for(int k=0; k<6; k++){
		int x = i + dR[k];
		int y = j + dC[k];

		if(x>=1 && x<=n && y>=1 && y<=m){
			if(k==0 || k==2 || k==4){
				sum1 += arr[x][y];
				temp1 = max(temp1, sum1);
				count1++;
			}
			else if(k==1 || k==3 || k==5){
				sum2 += arr[x][y];
				temp2 = max(temp2, sum2);
				count2++;
			}
		}

	}

	if(count1 == 3){
		Max = max(Max, temp1);
	}
	if(count2 == 3){
		Max = max(Max, temp2);
	}

}

void reset(){

	int n1 = 2*n;
	int m1;
	if(m%2==1)
		m1 = 2*(m/2+1);
	else
		m1 = 2*(m/2);

	for(int i=1; i<=n1; i++){
		for(int j=1; j<=m1; j++){
			arr[i][j] = 0;
		}
	}
}

void reset1(){
	for(int i=1; i<=2 * n; i++){
		for(int j=1; j<=m; j++){
			visited[i][j] = 0;
		}
	}
}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> m >> n;

		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				cin >> mt[i][j];
			}
		}

		reset();

		int indexx = 1;
		for(int i=1; i<=n; i++){
			int indexy = 1;
			for(int j=1; j<=m; j++){

				if(j%2==1){
					arr[indexx][indexy++] = mt[i][j];
				}else{
					arr[indexx+1][indexy++] = mt[i][j];
				}

			}

			indexx+=2;
		}

		n = 2*n;
		if(m%2==1)
			m = 2*(m/2+1);
		else
			m = 2*(m/2);

		Max = -1;

		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				if(arr[i][j] != 0){

					reset1();
					visited[i][j] = 1;
					BackTrack(i, j, 1, arr[i][j]);
					check(i, j);

				}
			}
		}

		cout << "Case #" << tc << endl;
		cout << Max * Max << endl;
		
	}
	return 0;
}