Greedy for Gold

0

0 votes
Dynamic programming, Easy
Problem

Queen Cersei's secret vault is full of gold coins. The floor of the vault is covered with RxC square tiles i.e R rows and C columns of tiles. Each tile has some gold coins.
Being the Queen's loyal servant, you are given the opportunity to go through the vault once and collect as many gold coins as possible.

Following are the rules:

  1. You can start from any tile in the first row and pick up the gold coins on that tile. 
  2. Then you can step on a tile in the next row either directly in front of the current tile, or diagonally to the left or right, and pick up the gold coins on that tile.
  3. You can continue step2 till you reach the last row.

Given the values of R and C, and the number of gold coins on each tile, find out the maximum number of coins you can have when you come out of the vault.

Input:

1st line:         T, the number of test cases. 

In each of the test cases,
1st line:         R and C, the number of rows and columns of tiles in the vault.
Next R lines: ith line specifies the number of gold coins on each tile of the ith row. Each line has C integers, where each integer G is the number of gold coins on that tile. The integers are separated by a space character.

Constraints:

  • 1<=T<=100
  • 1<=R<=100
  • 1<=C<=100
  • 0<=G<=100

Output:

The output should consist of T lines.
Each line consists of a single integer, which is the maximum possible number of gold coins you can collect from the first row to the last row for the corresponding test case.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
4 + 3 + 5 + 1 = 13 
Editor Image

?