---
title: "方格取数"
created: 2025-11-28
tags:
  - 算法
---

# 方格取数

## 题目 [方格取数](https://www.acwing.com/solution/content/51234/)

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。

![[image-77d678da.png]]

某人从图中的左上角A出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。

在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入格式

第一行为一个整数N，表示 N×N 的方格图。

接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行,该列上所放的数.

行和列编号分别从1,1开始。

一行“0 0 0”表示结束。

输出格式

输出一个整数,表示两条路径上取得的最大的和

数据范围

N<=10

样例

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

## 思路分析

起点 (1,1)，终点 (n,n)，每次规定只能向右或向下走

我们可以从起点出发两次，但同一个格子在两次路径中都经过的话，他的物品价值只会被累加 1次

问两次路线，途径格子的物品的总价值最大是多少

题目要求我们从起点先后出发两次

但我们可以规定两次是同时出发的，因为这两种方案的所有路线都是一一对应的

为什么这么映射呢？因为这样子做的话，我们可以轻松的处理两次路线走到同一个格子的情况

由此我们就可以把路径长度，作为DP的阶段

每个阶段中，我们同时把两条路径扩展一步，即路径长度加 1，来进入下一个阶段

而路径长度加1后，无非就是向下走一格或是向右走一格，对应横纵坐标的变换

根据k,x1,y1,x2,y2的关系，我们可以获得如下等式

x1+y1=x2+y2=k

获得上述等式以后，我们就可以通过三个维度来描述状态了，分别是k,x1,x2 于是，状态的初值为f[2][1][1]，目标状态为f[2 \* n][n][n]

（用原始的x1,y1 x2,y2也是可以的 但是因为有4维 可能导致效率很低 所以得想一个办法 既能表示出x1,y1和x2,y2又能降低维度
用一个k去记录总步数

（或者说是横纵坐标的总和 因为每次都在往右或往下走 这个总和是会一直加的 且在同一时刻 第一条路径和第二条路径的k是一样大的） 然后就只需要记录x1和x2即可
至于y1,y2可以用k-x1 和k-x2求出 这样一来 能用一个三维的状态数组表示出从起点走到x1,y1和x2,y2的总价值的最大值）


那么对于如何判断两次路线走进了同一个方格里，直接用x1=x2来判断了

当x1≠x2，当前两条路线走到的格子不是同一个，v=w(x1,k−x1)+w(x2,k−x2) 当x1=x2，当前两条路线走到了同一个格子中，则v=w(x1,k−x1)

![[image-e69843a3.png]]

`f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;`

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 15, M = 2 * N;

int n;
int a, b, c;
int w[N][N];
int f[M][N][N];

int main()
{
    cin >> n;
    while (cin >> a >> b >> c, a || b || c)
        w[a][b] += c;

    for (int k = 2; k <= 2 * n; ++ k)
    {
        for (int i = 1; i < k && i <= n; ++ i)
        {
            for (int j = 1; j < k && j <= n; ++ j)
            {
                int v = w[i][k - i];
                if (i != j) //判断两条路线是否经过同一个格子 经过的话只需要累加一次
                    v += w[j][k - j];
                f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;
            }
        }
    }

    cout << f[2 * n][n][n] << endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[数字三角形模型练习|数字三角形模型练习]] 🏠 [[00-刷题理模型]] ➡️ [[最低通行费|最低通行费]]