算法设计与分析: 3

算法设计与分析: 3"/>

算法设计与分析: 3

3-18 收集样本问题

问题描述

机器人 Rob 在一个有 n*n 个方格的方形区域 F 中收集样本。(i,j)方格中样本的价值 为 v(i,j)，如下图所示。

Rob 从方形区域 F 的左上角 A 点出发，向下或向右行走，直到右下角的 B 点，在走过的 路上，收集方格中的样本。Rob 从 A 点到 B 点共走 2 次，试找出 Rob 的 2 条行走路径，使其取得的样本总价值最大。

给定方形区域 F 中的样本分布，编程计算 Rob 的 2 条行走路径，使其取得的样本总价值最 大。

数据输入：
第 1 行有 1 个正整数 n，表示方形区域 F 有 n*n 个方格。 接下来每行有 3 个整数，前 2 个表示方格位置，第 3 个数为该位置样本价值。最后一行是 3 个 0。

Java

import java.util.Scanner;//沿着从A到B的对角线方向进行扫描，每次从左下到右上连线上最多取2个样本值
public class ShouJiYangBen {private static int n;//n X n个方格private static