Given a K * K matrix representing a field of crops, the goal is to collect as much crops as possible. Here are the rules for collecting crops:
- You can only move downward in a straight line in this field of crops. (Meaning from the top of the matrix to the bottom in a straight line).
- All crops within your path will get destroyed. And you can only collect crops to your left and right of your path. For example, you are at cell (1,1) in the matrix, you can then only collect crops at cell (1,0) and (1,2). You cannot collect the crop at (2,1), which is the cell below you since you can only collect crops left/right of your path.
Given the K * K matrix, return the maximum possible amount of crops that can be harvested based on the abovementioned rules of harvesting crops.
Input format:
K: the dimension of one side of the K * K matrix.
C: list of coordinates of crops (E.g. [(0,0), (1,2), (3,4)])
Output:
One integer representing maximum possible crops that can be harvested.
The inputs may not be 100% correct. For now, the two example images would be enough for you to understand the problem. I will modify the input nums once find more info. If you happen to know about them, feel free to contact Groot on discord server. TYSM in advance ^3~
Example 1:
Input: K = 3, C = [[0,1], [0,2], [1,0], [1,1], [2,0]]
Output: 14
Explanation:The "X" represents the path you took. In this case, we move downwards using the first and second column to collect the crops. The maximum crop harvested is 8+3+3 = 14 in this example. Note that the crop at (0,0) is destroyed since it was in your path. You can only harvested the crops at the sides (left/right) of your path.
Example 2:
Input: K = 3, C = [[0,2], [1,0], [1,1], [2,0], [2,1]]
Output: 18
Explanation:In this example, you are able to collect all crops without destroying any in your path. The optimal path is to move downwards on the second column all the way. And then later move down one step in the third column. Thus the answer is 1+3+3+8 = 18.
K <= 1 * 10^4
Number of crops <= 5 * 10^5
input:
output: