有n×n的方格数(n≤8),其中的某些方格中填入正整数表示该方格中的数字,而其他的方格中则放入数字0,表示该方格中没有数。如下图所示:
琪儿和琳琳分别从左上角出发,每人各走一次,可以向下行走也可以向右走,直到到达右下角,在走过的路上,可以取走方格中的数,取走的方格数将变为0,试找出两条这样的路径,使得取得的数之和最大。
输入的第一行为一个整数n,表示n×n的方格图,接下来每行有三个整数,前两个表示位置,第三个数为该位置上的数。一行单独的0表示输入结束。
两条路径上取得的最大和。
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
67