Problem D: Numbered Grid A grid of size N rows and M columns is filled with numbers, one in each cell. You start at the centre of the cell at the top-left corner (1,1) and your destination is the centre of the cell at the bottom- right corner(N,M). In each step, you are only allowed to move to the centre of the cell to the right or to the centre of the cell to the bottom. There are many paths you can take to reach your destination from your start - however, every path can be uniquely broken down into a series of straight line-segments joined at right-angles. Each straight line-segment in your path is termed a 'leg' of your path. Your task is to choose a subset of the cells along your path in such a way that the sum of the numbers in the chosen cells is maximized. Your choice of cells must be such that exactly one chosen cell is present on each leg of the path. Note that cells at the intersection of two legs belong to both legs. What is the maximum possible sum you can form? Input Format:
The first line contains one integer T, the number of testcases. The first line of each test case contains two space-separated integers N and M. Each of the next N lines contains M space separated integers, denoting cell values. The jth integer in the ith line denotes the value of the cell (i, j). Constraints: 1 <= T <= 10 1 <= N, M <= 100 Numbers in each cell will be between -10000 and 10000 inclusive. Output Format: For each testcase output a single line containing the maximum sum you can form. Sample Input: 3 2 2 -1 -2 5 -1 3 4 -1 2 -3 -4 -2 -3 5 -2 -1 -1 -2 3 2 2 3 1 5 3 Sample Output: 5 10 6 Explanation: In the first test case, you can first move down and then move right. Your path now has 2 legs and you can choose only the cell containing 5. This is valid as it satisfies the condition that you must choose exactly one cell in each leg (because 5 is a part of both legs). In the second test case, one best path is to walk right, choose 2, go right again and then down to choose 5, go further down and then right to pick up the final 3 (There are also other ways to pick-up the same numbers). In the third test case, the best path is either (down, right) or (right, down). Note that since you can pick-up only one number in each leg you cannot select the '5' in the lower left corner (If you decide to pick-up 5, then you cannot pick up any other number because '5' is shared by both legs. We can do better by selecting both 3s). Time limit: 2 seconds Memory: 64 MB ACM International Collegiate Programming Contest, 2010, Asia- Amritapuri Site -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
