Going Fishing:
Problem:
Good News!! The Planet Express crew are going fishing! and Bender is doing so the way robots are meant to do it: with dynamite!. Using sophisticated robot technology, Bender is scanning the surrounding area with a sonar device. The sonar’s data represents the area around Bender as a grid, with the number of fish in each cell of the grid.
Ahhh… the joys of fishing
Help Bender figure out where to throw his dynamite stick to catch the maximum number of fish. Bender has only one dynamite stick and it explodes in a peculiar way: It blows horizontally and vertically across the water ( think bomberman )
Input:
The first line of the input states the number of test cases T, then T test cases follow. Each test case consists of a data grid. A test case begins with the numbers H and W; the height and width of the sonar data grid. H rows of W data points follow, describing the number of fish detected by the sonar.
Output:
For each test case, output one line containing "#t: at (r, c) Bender catches f fish.", where t is the test case number (starting from 0), (r, c) are the row,columns where throwing the dynamite stick maximizes the number of fish caught and f is the number of fish caught.
Implementation Requirements:
Given that you do not know beforehand how large a sonar data grid is, your program should dynamically allocate a 2D Array after the width and height of a grid is read. Make sure to de-allocate the 2D Array after you find the answer and before your program moves on to process the next grid.
Sample:
Input
Output
3
5 8
1 0 0 1 1 0 0 1
0 1 0 1 0 1 0 1
0 2 1 3 1 2 0 0
0 3 1 1 2 3 1 3
0 0 3 7 2 2 1 0
6 6
4 1 2 0 0 6
6 7 5 9 1 3
3 4 6 2 1 1
1 0 0 3 1 3
0 1 0 1 1 2
0 2 1 4 3 0
7 12
2 6 2 6 2 2 4 1 2 5 2 1
1 0 0 3 1 3 0 0 1 0 1 1
0 2 1 4 3 0 0 1 0 1 1 0
1 3 1 2 0 0 0 1 0 1 1 0
0 3 1 1 8 3 8 3 0 0 1 2
0 0 3 7 2 0 3 1 3 0 1 1
0 0 0 3 0 1 1 0 1 1 0 0
#0: at (3,3) Bender catches 26 fish.
#1: at (1,5) Bender catches 43 fish.
#2: at (0,3) Bender catches 55 fish.
