AcWing 60. 礼物的最大价值
宋标 Lv5
  2022-08-18 02:31:00 2022-08-18 02:31    

题目

在一个 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 ）。

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

注意：

样例：

输入：
[
  [2,3,1],
  [1,7,1],
  [4,6,1]
]

输出：19

解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

题解

单源bfs
切记边界和剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define N 1355

class Solution {
public:

    int matrix[N][N];

    int getMaxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        queue<pair<int, int>> qe;
        qe.push({0, grid[0][0]});
        matrix[0][0] = grid[0][0];

        int dx[] = {0, 1}, dy[] = {1, 0};
        while (qe.size())
        {
            auto t = qe.front(); qe.pop();
            int xy = t.first, v = t.second;

            int x = xy / m, y = xy % m;
            for (int i = 0; i < 2; ++ i)
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < m && v + grid[a][b] > matrix[a][b])
                {
                    matrix[a][b] = v + grid[a][b];
                    qe.push({a * m + b, v + grid[a][b]});
                }
            }

        }

        return matrix[n - 1][m - 1];
    }
};
 评论