Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.3 kB
1
Indexable
Never
Hugo và chị ong nâu nấu nâu nấu lầu nâu
Hugo và chị ong nâu là hàng xóm của nhau. Tuy nhiên Hugo thì lười nhưng lại muốn lấy mật ăn, còn chị ong nâu thì chăm chỉ kiếm mật để đầy tổ của mình. Vì thèm ăn mật ong mà mãi chị ong nâu không cho nên sau 1 thời gian nằm gai nếm mật rình mò Hugo đã phát hiện ra các bố trí của các thùng chứa mật và số mật trong mỗi thùng ở nhà chị ong nâu. Mật ở nhà chị ong nâu được biểu diễn bằng 1 ma trận NxM ô, mỗi ô một thùng mật. Mỗi ô chứa lượng mật nhất định và có thể liên kết với 6 ô xung quanh theo cách bố trí của tổ ong. 2 ô được gọi là có liên kết nếu chúng có chung cạnh.

Hôm nay Hugo phát hiện chị ong nâu đi sang khu rừng bên cạnh để lấy mật. Hugo sẽ vào nhà chị ong nâu để ăn trộm mật ong của chị. Để không bị phát hiện Hugo chỉ có thể lấy tối đa 4 thùng ở 4 ô có liên kết với nhau. Hãy giúp Hugo tìm ra bình phương tổng lượng mật lớn nhất có thể lấy.

Ex: M = 5 , N = 3



Trong ví dụ trên, bình phương tổng lượng mật là

(300 + 410 + 185 + 95)2 = 980100

 



Trong ví dụ trên Hugo sẽ bị phát hiện và không thể lấy mật.

 

[Input]

- Dòng đầu tiên là số thử nghiệm T (T <= 50)

- Mỗi TC :

         + Dòng đầu tiên chưa kích thước ma trận M, N ( 3 ≤ N, M ≤ 15 )

         + Trong N dòng tiếp theo, lượng mật C ở mỗi ô sẽ được cho theo quy tắc bên dưới (0 ≤ C ≤ 1000)



5

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

 

[Output]

Ghi ra bình phương tổng lượng mật

Case #1

2250000

Case #2

3748096

Case #3

3928324

Case #4

7236100

Case #5

13104400
//////////////////////////////////////////
#include<iostream>
using namespace std;
int M,N,a[16][16],ans,vs[16][16];
int dxl[6]={-1,-1,-1,0,0,1};
int dyl[6]={-1,0,1,-1,1,0};
int dxc[6]={1,1,1,0,0,-1};
int dyc[6]={-1,0,1,-1,1,0};
bool checkbien(int x,int y){
	if(x>=1 && x<=M && y>=1 && y<=N){
		return true;
	}
	return false;
}
void reset(){
	for(int i=1;i<=M;i++){
		for(int j=1;j<=N;j++){
			vs[i][j]=0;
		}
	}
}
void bt(int k,int x,int y,int sum){
	if(k==4 ){
		if(sum>ans)ans=sum;
		return;
	}
	for(int i=0;i<6;i++){
		int xx,yy;
		if(y%2==1){
			xx=x+dxl[i];
			yy=y+dyl[i];
		}
		if(y%2==0){
			xx=x+dxc[i];
			yy=y+dyc[i];
		}
		if(checkbien(xx,yy) && vs[xx][yy]==0){
			vs[xx][yy]=1;
			bt(k+1,xx,yy,sum+a[xx][yy]);
			bt(k+1,x,y,sum+a[xx][yy]);
			vs[xx][yy]=0;
		}
		
	}
}
int main(){
	int T;
	//freopen("Text.txt","r",stdin);
	cin>>T;
	for(int tc=1;tc<=T;tc++){
		cin>>N>>M;
		for(int i=1;i<=M;i++){
			for(int j=1;j<=N;j++){
				cin>>a[i][j];
			}
		}
		ans=0;
		for(int i=1;i<=M;i++){
			for(int j=1;j<=N;j++){
				reset();
				vs[i][j]=1;
				bt(1,i,j,a[i][j]);
			}
		}
		cout<<"Case #"<<tc<<endl<<ans*ans<<endl;
	
	}
	return 0;
}