【算法分析与设计】双胞胎探宝

问题描述：
现有一对双胞胎，在一个有n * n个方格的方形宝藏区域F中探宝。（i,j）方格中宝物的价值为v(i,j)，如下图所示。
A
3 2
5
7 1
9 B
双胞胎均从F的A点出发，向下或向右行走，直到B点，在走过的路上，收集方格中的宝藏。试找出兄弟二人可以获得的宝藏总价的值最大。
数据输入：
输入数据第1行有1个正整数n，表示方形区域F有n * n个方格。 接下来每行有3个整数，前2个表示方格位置，第3个数为该位置宝藏价值。最后一行是3个0。
样例输入：
8 2 2 3 2 5 2 3 4 5 4 1 7 4 3 1 5 2 9 0 0 0
样例输出：
24
代码：

#include <stdio.h>
#define MAXN 100
int n;              // 方形区域边长
int g[MAXN][MAXN];  // 样本（宝物）价值
int h[MAXN][MAXN][MAXN][MAXN];  // 记录路径的最大样本价值

void val(int x1, int y1, int x2, int y2, int v);
void dyna();

int main() 
{
    scanf("%d", &n);  // 输入方形区域边长，n*n 方格

    // 输入样本价值
    int x, y, v;
    while (1) 
    {
        scanf("%d %d %d", &x, &y, &v);
        if (x == 0 && y == 0 && v == 0) 
        {
            break;
        }
        g[x][y] = v;
    }

    dyna();  // 求解最大样本价值

    // 输出最大样本价值
    printf("%d\n", h[n][n][n][n]);

    return 0;
}

void val(int x1, int y1, int x2, int y2, int v) 
{
    if (x1 == x2 && y1 == y2) 
    {
        h[x1][y1][x2][y2] = h[x1][y1][x2][y2] > v + g[x1][y1] ? h[x1][y1][x2][y2] : v + g[x1][y1];
    } 
    else 
    {
        h[x1][y1][x2][y2] = h[x1][y1][x2][y2] > v + g[x1][y1] + g[x2][y2] ? h[x1][y1][x2][y2] : v + g[x1][y1] + g[x2][y2];
    }
}

void dyna() 
{
    int x1, y1, x2, y2, s, v;
    for (int i = 0; i <= n; i++) 
    {
        for (int j = 0; j <= n; j++) 
        {
            for (int k = 0; k <= n; k++) 
            {
                for (int l = 0; l <= n; l++) 
                {
                    h[i][j][k][l] = 0;
                }
            }
        }
    }

    h[1][1][1][1] = g[1][1];
    for (s = 2; s <= n + n - 1; s++) 
    {
        for (x1 = 1; x1 <= s - 1; x1++) 
        {
            for (x2 = 1; x2 <= s - 1; x2++) 
            {
                y1 = s - x1;
                y2 = s - x2;
                v = h[x1][y1][x2][y2];
                val(x1 + 1, y1, x2 + 1, y2, v);
                val(x1 + 1, y1, x2, y2 + 1, v);
                val(x1, y1 + 1, x2 + 1, y2, v);
                val(x1, y1 + 1, x2, y2 + 1, v);
            }
        }
    }
}