矩阵查询可获得的最大分数

题目

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

---

给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。

找出一个大小为 k 的数组 answer ，且满足对于每个整数 queres[i] ，你从矩阵 左上角 单元格开始，重复以下过程：

• 如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。
• 否则，你不能获得任何分，并且结束这一过程。

在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

返回结果数组 answer 。

示例 1：

输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
输出：[5,8,1]
解释：上图展示了每个查询中访问并获得分数的单元格。

示例 2：

输入：grid = [[5,2,1],[1,1,2]], queries = [3]
输出：[0]
解释：无法获得分数，因为左上角单元格的值大于等于 3 。

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10^5
• k == queries.length
• 1 <= k <= 10^4
• 1 <= grid[i][j], queries[i] <= 10^6

题解

方法一：

思路

并查集做法

对于查询离线处理，将queries升序排序。

然后对于queries[i]，我们将矩阵中单元格所有值小于queries[i]的四周尝试连接（对于四周的值严格小于queries[i]即可连接）。对于queries[i]的答案就是查询并查集包含(0,0)单元格的集合大小。

如何实现将矩阵中所有值小于queries[i]的四周尝试连接。首先可以对矩阵按照（值，x，y）三元组字典序升序排序。接下来就可以用双指针高效处理值小于queries[i]的单元格。

代码

class Solution {
public:
    vector<int> maxPoints(vector<vector<int>>& g, vector<int>& q) {
        int n = g.size(), m = g[0].size(), sz = n*m;
        //并查集
        int st[sz]; memset(st, -1, sizeof(st));
        function<int(int)> ufind = [&](int x) {
            return st[x]<0 ? x : st[x] = ufind(st[x]);
        };
        //对矩阵离线处理
        array<int,3> a[sz];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i*m+j] = {g[i][j], i, j};
            }
        }
        sort(a, a+sz);
        //查询离线处理
        int qsz = q.size();
        vector<int> id(qsz);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int x, int y) {return q[x]<q[y];});
        //将小于q[i]的相邻的点纳入同一集合。然后查询包含左上顶点的集合大小。
        vector<int> ans(qsz);
        int p = 0;
        for (int i:id) {
            int v = q[i];
            while (p<sz && a[p][0] < v) {
                for (int j=0; j<4; j++) {
                    int x = a[p][1] + (j-1)%2;
                    int y = a[p][2] + (j-2)%2;
                    if (x<0 || x>=n || y<0 || y>=m || g[x][y]>=v) continue;
                    int fa = ufind(a[p][1]*m+a[p][2]), fb = ufind(x*m+y);
                    if (fa != fb) {
                        st[fa] += st[fb];
                        st[fb] = fa;
                    }
                }
                p++;
            }
            if (g[0][0] < v) ans[i] = -st[ufind(0)];
        }
        return ans;
    }
};

方法二：

思路

优先队列
对于查询离线处理，将queries升序排序。
我们动态的维护一个最小值优先队列，保证每个元素只会入队出队一次。
对于queries[i]，我们队列中小于queries[i]的值全部取出，然后在取出的同时将相邻的未入队的元素入队。这一次查询的答案就是所有已出队的元素个数。

代码

class Solution {
public:
    vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
        priority_queue<array<int,3>, vector<array<int,3>>, greater<>> q;
        int n = grid.size(), m = grid[0].size(), sz = queries.size();
        vector<int> id(sz), ans(sz);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int a, int b){return queries[a]<queries[b];});
        q.push({grid[0][0], 0, 0});
        grid[0][0] = 0;
        int cnt = 0;
        for (int i:id) {
            int v = queries[i];
            while (q.size() && q.top()[0] < v) {
                auto [val, x, y] = q.top(); q.pop(); cnt++;
                for (int j=0; j<4; j++) {
                    int dx = x+(j-1)%2;
                    int dy = y+(j-2)%2;
                    if (dx<0 || dx>=n || dy<0 || dy>=m || !grid[dx][dy]) continue;
                    q.push({grid[dx][dy], dx, dy});
                    grid[dx][dy] = 0;
                }
            }
            ans[i] = cnt;
        }
        return ans;
    }
};