# Untitled

unknown

plain_text

a year ago

1.1 kB

0

Indexable

Never

^{}

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