hugo_chi_ong_nau.txt

#include <iostream>
using namespace std;
int dxl[]={-1,0,0,1,1,1};
int dyl[]={0,-1,1,-1,0,1};
int dxc[]={-1,-1,-1,0,0,1};
int dyc[]={-1,0,1,-1,1,0};
int M,N, maxx;
int a[18][18], visit[18][18];

void nhap(){
	cin >> M >> N;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			cin >> a[i][j];
			visit[i][j] = 0;
		}
	}
}
void backtrack(int r, int c, int cnt, int res){
	if(cnt==4){
		if(maxx < res) maxx = res;
		return;
	}
	//if(res < maxx)	return;
	if(c%2 != 0){
		for(int i=0; i<6; i++){
			int nx = r + dxl[i];
			int ny = c + dyl[i];
			if(nx>=0 && nx<N && ny>=0 && ny<M && visit[nx][ny]==0){
				visit[nx][ny] = 1;
				res += a[nx][ny];
				cnt++;
				//cout << a[nx][ny];
				backtrack(nx,ny,cnt,res);
				backtrack(r,c,cnt,res);
				visit[nx][ny] = 0;
				res -= a[nx][ny];
				cnt--;
			}
		}
	}
	if(c%2 == 0){
		for(int i=0; i<6; i++){
			int nx = r + dxc[i];
			int ny = c + dyc[i];
			if(nx>=0 && nx<N && ny>=0 && ny<M && visit[nx][ny]==0){
				visit[nx][ny] = 1;
				res += a[nx][ny];
				cnt++;
			//	cout << a[nx][ny];
				backtrack(nx,ny,cnt,res);
				backtrack(r,c,cnt,res);
				visit[nx][ny] = 0;
				res -= a[nx][ny];
				cnt--;
			}
		}
	}
}

int main(){
	freopen("INP.txt","r",stdin);
	int T; cin >> T;
	for(int tc=1; tc<=T; tc++){
		nhap();
		maxx = -1;
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				visit[i][j] = 1;
				backtrack(i,j,1,a[i][j]);
				visit[i][j] = 0;
			}
		}
		cout << "Case #" << tc << endl;
		cout << maxx*maxx << endl;
	}
	return 0;
}