# hugo_chi_ong_nau.txt

user_9278292
plain_text
7 months ago
1.6 kB
8
Indexable
Never
```#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;
}```