Untitled

Mario Climb

0	0	1	3
1	1	1	0
0	0	0	0
2	1	1	1

Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3
0 là nhữngô Mario không thể qua
1 là nhữngô Mario có thể qua
2 là vị trícủa Mario
3 là vị trí Mario cần di chuyển đến
Các vị trí này được thể hiện bằng ma trận NxM( 2<=N,M<=50)
Mario có thểdi chuyển theo hàng ngang hoặc hàng dọc
Hàng ngang mario chỉ nhảy được tối đa 1 bước
Hàng dọc mario có thể nhảy được “h” bước
Tìm bước nhảy “h” tối thiểu để Mario có thể ăn được vàng
Sample Input
3
5 8
1 1 1 1 0 0 0 0
0 0 0 3 0 1 1 1
1 1 1 0 0 1 0 0 
0 0 0 0 0 0 1 0
2 1 1 1 1 1 1 1
5 6
0 1 1 1 0 0
3 1 0 1 1 0
0 0 0 0 1 1
0 0 0 0 0 1
2 1 1 1 1 1
9 13
0 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 0 0 0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 0 0 0 1 3 
0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1
Sample output
Case #1
2
Case #2
1
Case #3
3
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
[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