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:↵
↵
https://github.com/yawn-lento/yawn-s-codes/blob/main/P1004%20%E5%8F%8C%E5%B1%82%E9%9A%8F%E6%9C%BA%E5%B5%8C%E5%A5%97%E5%B0%9D%E8%AF%95.cpp
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:↵
↵
https://github.com/yawn-lento/yawn-s-codes/blob/main/P1004%20%E5%8F%8C%E5%B1%82%E9%9A%8F%E6%9C%BA%E5%B5%8C%E5%A5%97%E5%B0%9D%E8%AF%95.cpp




