Original: link

Problem: 2503. 矩阵查询可获得的最大分数

思路

广度优先搜索

解题方法

维护一个哈希表$dict[time: int, value: int]$表示单次查询$q \ge time$时所能获得的最大分数

所以在从$grid(0, 0)$出发的广度优先搜索中，每次拓展节点时维护当前遍历过所有节点的个数$sum$（分数）与最大值$max$，更新$dict[max] \leftarrow sum$

所以搜索中每次拓展节点时选择$grid$值最小的节点，以维护$dict$的正确性，否则会漏掉一些可以遍历到的点，使用$std::priority\_queue$维护小根堆存储拓展节点队列

哈希表排序后，对于查询数组二分查找获得答案

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(mn\times log(mnk))$

• 空间复杂度:

添加空间复杂度, 示例： $O(mn)$

Code

using xy = pair<int, int>;
using wxy = pair<int, xy>;
constexpr std::array<xy, 4> dirs{{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}};
class Solution {
public:
  vector<int> maxPoints(vector<vector<int>> &grid, vector<int> &queries) {
    using u8 = uint8_t;
    auto m = grid.size(), n = grid[0].size(), l = queries.size();

    vector vis(m, vector(n, u8{}));
    std::priority_queue<wxy, vector<wxy>, greater<>> q;
    q.emplace(grid[0][0], xy{0, 0});
    vis[0][0] = true;

    std::unordered_map<int, int> threshold2value;
    int cur_sum = 0, cur_max = 0;

    //广度优先搜索
    while (!q.empty()) {
      auto [cur, pos] = q.top();
      q.pop();

      cur_max = max(cur_max, cur);
      ++cur_sum;

      threshold2value[cur_max] = cur_sum;

      for (auto [dx, dy] : dirs) {
        auto nx = pos.first + dx, ny = pos.second + dy;
        if (nx < m && nx > -1 && ny > -1 && ny < n && !vis[nx][ny])
          vis[nx][ny] = true, q.emplace(grid[nx][ny], xy{nx, ny});
      }
    }

    //排序后二分查找
    vector<xy> kv(threshold2value.begin(), threshold2value.end());
    std::sort(kv.begin(), kv.end());
    std::transform(
        queries.begin(), queries.end(), queries.begin(), [&kv](int q) {
          auto iter = std::upper_bound(kv.begin(), kv.end(), xy{q, 0});
          if (iter == kv.begin())
            return 0;
          return std::prev(iter)->second;
        });
    return queries;
  }
};