hugoandbee

#include <iostream>

using namespace std;


int dx_odd[] = { -1,0,0,1,1,1 };
int dy_odd[] = { 0,-1,1,-1,0,1 };
int dx_even[] = { -1,-1,-1,0,0,1 };
int dy_even[] = { -1,0,1,-1,1,0 };
int map[18][18];
int visited[18][18];

int col, row;
int res;


void back(int r, int c, int cnt, int sum) {
	if (cnt == 4) {
		if (res < sum) res = sum;
		return;
	}
	if (c % 2 != 0) {
		for (int i = 0; i < 6; i++) {
			int nx = r + dx_odd[i];
			int ny = c + dy_odd[i];
			if (nx >= 0 && nx < row && ny >= 0 && ny < col && visited[nx][ny] == 0) {
				visited[nx][ny] = 1;
				back(nx, ny, cnt + 1, sum + map[nx][ny]);
				back(r, c, cnt + 1, sum + map[nx][ny]);
				visited[nx][ny] = 0;

			}
		}
	}
	if (c % 2 == 0) {
		for (int i = 0; i < 6; i++) {
			int nx = r + dx_even[i];
			int ny = c + dy_even[i];
			if (nx >= 0 && nx < row && ny >= 0 && ny < col && visited[nx][ny] == 0) {
				visited[nx][ny] = 1;
				back(nx, ny, cnt + 1, sum + map[nx][ny]);
				back(r, c, cnt + 1, sum + map[nx][ny]);
				visited[nx][ny] = 0;
			}
		}
	}
}

int main()
{
	int T;
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		res = -1;
		cin >> col >> row;
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				cin >> map[i][j];
				visited[i][j] = 0;
			}
		}
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				visited[i][j] = 1;
				back(i, j, 1, map[i][j]);
				visited[i][j] = 0;
			}
		}
		cout << res * res << endl;
	}
	return 0;
}