# Untitled

unknown
plain_text
a year ago
3.2 kB
2
Indexable
Never
```Base Station == Hugo nau nau

Given the map of BTS consists of N x M cells. Each cell in map have a cost and can connect to other 6 cells around it. Two cells are connected if they share a same edge.
We call a group of 4 connected cells a cluster. Your program should find the cluster with highest cost sum and print out the square value of its sum
Ex: M = 5 , N = 3

In above example, we have a cluster with square of sum
(300 + 410 + 185 + 95)2 = 980100

In above example, the selected cells is not a cluster.

[Input]
- The first line is the number of test cases T (T <= 50)
- In each TC :
+ The first line give the size of the map M, N ( 3 ≤ N, M ≤ 15 )
+ In the next N lines, the cost C (0 ≤ C ≤ 1000) of each cell is given as below rule

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]
Print out the square value of maximum cluster's sum
Case #1
2250000
Case #2
3748096
Case #3
3928324
Case #4
7236100
Case #5
13104400

Code:
#include<iostream>

using namespace std;

enum parity {EVEN = 0, ODD = 1};

int visited1[20][20];
int N; // number rows
int M; // number colums
int map[20][20]; // map mat ong

void reset1()
{
for(int i =0; i< 20; i++)
for(int j =0; j< 20; j++)
{
visited1[i][j] = false;
}
}

int dxEven[6] = {0,-1,0,1,1,1};
int dyEven[6] = {-1,0,1,1,0,-1};

int dxOdd[6] = {-1,-1,-1, 0, 1, 0};
int dyOdd[6] = {-1, 0, 1, 1, 0,-1};

bool visited[20][20];

parity isParity(int i)
{
if(i % 2 == 0)
return ODD; // vi tri le
return EVEN;
}

bool isSafe(int x, int y)
{
if(x >= 0 && x < N && y >= 0 && y < M)
return true;
return false;
}

int maxSum;

void backTrack(int k,int x, int y, int sum)
{
if(k == 3)
{

if(sum > maxSum)
{
reset1();
for(int i =0; i< 20; i++)
for(int j =0; j< 20; j++)
{
visited1[i][j] = visited[i][j];
}
maxSum = sum;
}
return;
}
for(int i = 0; i < 6; i++)
{
int xx, yy;
if(isParity(y) == EVEN)
{
xx = x + dxEven[i];
yy = y + dyEven[i];
}
else if(isParity(y) == ODD)
{
xx = x + dxOdd[i];
yy = y + dyOdd[i];
}
if(isSafe(xx,yy) && !visited[xx][yy])
{
visited[xx][yy] = true;
backTrack(k+1,xx,yy, sum + map[xx][yy]);
backTrack(k+1,x,y, sum + map[xx][yy]);
visited[xx][yy] = false;
}
}
}

void input()
{
cin>>M>>N;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
cin>>map[i][j];
}
}
}

void reset()
{
for(int i =0; i< 20; i++)
for(int j =0; j< 20; j++)
{
visited[i][j] = false;
}
}

int main()
{
freopen("Text.txt","r",stdin);

int T;
cin>>T;
for(int tc = 1; tc <= T; tc++)
{
input(); // nhap input N, M, ma tran value mat ong
reset();
maxSum = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j< M; j++)
{
visited[i][j] = true;
backTrack(0,i,j,map[i][j]);
reset();
}
int ans = maxSum;
cout<<"Case #"<<tc<<endl;
cout<<ans*ans<<endl;
}

return 0;
}```