Untitled

#include <iostream>

using namespace std;

int T, N, M;
int arr[20][20];
int visited[20][20];
int ans, value;

int X1[6] = {-1, 0, 1, 1, 1, 0};
int Y1[6] = {0, 1, 1, 0, -1, -1};

int X2[6] = {-1, -1, 0, 1, 0, -1};
int Y2[6] = {0, 1, 1, 0, -1, -1};

void backtrack(int row, int col, int cnt){
	if(cnt == 4){
		if(ans > value){
			value = ans;
		}
		return;
	}

	for(int i = 0; i < 6; i++){
		int nr, nc;
		if(col % 2 == 1){
			nr = row + X1[i];
			nc = col + Y1[i];
		}else{
			nr = row + X2[i];
			nc = col + Y2[i];
		}
		if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0){
			ans += arr[nr][nc];
			visited[nr][nc] = 1;
			backtrack(nr, nc, cnt + 1);
			backtrack(row, col, cnt + 1);
			visited[nr][nc] = 0;
			ans -= arr[nr][nc];
		}
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> M >> N;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				cin >> arr[i][j];
			}
		}
		value = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){

				for(int k = 0; k < N; k++){
					for(int h = 0; h < M; h++){
						visited[k][h] = 0;
					}
				}

				ans = arr[i][j];
				visited[i][j] = 1;
				backtrack(i, j, 1);
			}
		}
		cout << "Case #" << tc << endl;
		cout << value * value << endl;
	}
	return 0;
}

TC:
2
5 3
300 410 150 55 370
120 185 440 190 450
165 70 95 420 50
5 5
356 55 41 453 12
401 506 274 506 379
360 281 421 311 489
425 74 276 371 164
138 528 461 477 470