Title: Grid Access (NOIP 2000) Problem Description: There is an N×N grid (N≤9). Some cells contain positive integers, while others contain 0.
A person starts from the top-left cell A and walks to the bottom-right cell B. He can only move downward or rightward during the walk.
When he passes through a cell, he takes the number in that cell (the number becomes 0 after being taken).
Now, this person needs to walk from A to B twice. Find the maximum possible sum of the numbers taken from the two paths.
Input Format: The first line contains a single integer N, representing the size of the grid. The following lines contain triples of integers x,y,v, where v is the integer placed in the cell at row x and column y.
The input is terminated by a single line containing 0 0 0.
Output Format: Output a single integer, representing the maximum total sum of the numbers collected on the two paths.
Sample Input:
8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0
Sample Output:
67
Constraints:
1≤N≤9,1≤x,y≤N,1≤v≤30
Using two layer of Monte Carlo and Greey algorithm, I managed to gain AC, though still achievable at small numbers.
below are my codes in Github:








