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

链接：2503.矩阵查询可获得的最大分数
难度：Hard
标签：广度优先搜索、并查集、数组、双指针、矩阵、排序、堆（优先队列）
简介：给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。返回结果数组 answer 。

题解 1 - cpp

• 编辑时间：2022-12-11
• 执行用时：264ms
• 内存消耗：30.5MB
• 编程语言：cpp
• 解法介绍：对 query 排序后，从小往大找， 对于所有小于 q 的数字进行并查集合并。

class UnionFind {
public:
    int n;
    vector<int> data, cnt;
    UnionFind(int n): n(n), data(vector<int>(n, 0)), cnt(vector<int>(n, 1)) {
        for (int i = 0; i < n; i++) data[i] = i;
    }
    int size(int v) {
        return cnt[find(v)];
    }
    int find(int v) {
        if (data[v] == v) return v;
        return data[v] = find(data[v]);
    }
    void uni(int v1, int v2) {
        int p1 = find(v1), p2 = find(v2);
        if (p1 != p2) {
            cnt[p1] += cnt[p2];
            data[p2] = p1;
        }
    }
};
int pos2Idx(int x, int y, int size) {
    return x * size + y;
}
void idx2Pos(int idx, int size, int &x, int &y) {
    x = idx / size;
    y = idx % size;
}
vector<vector<int>> dirs = {
    {0, 1}, {0, -1},
    {1, 0}, {-1, 0}
};
class Solution {
public:
    int n, m, qs;
    vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
        n = grid.size();
        m = grid[0].size();
        qs = queries.size();
        vector<int> ans(qs, 0), list(qs), data;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) data.push_back(pos2Idx(i, j, m));
        sort(data.begin(), data.end(), [&](auto &i1, auto &i2){
            int x1, y1, x2, y2;
            idx2Pos(i1, m, x1, y1);
            idx2Pos(i2, m, x2, y2);
            return grid[x1][y1] < grid[x2][y2];
        });
        iota(list.begin(), list.end(), 0);
        sort(list.begin(), list.end(), [&](auto &i1, auto &i2){ return queries[i1] < queries[i2]; });
        /*
        cout << "data : ";
        for (auto &idx : data) {
            int x, y;
            idx2Pos(idx, m, x, y);
            cout << "(" << x << ", " << y << ", " << grid[x][y] << "), ";
        }
        cout << "none" << endl;
        cout << "list : ";
        for (auto &idx : list) {
            cout << "(" << idx << ", " << queries[idx] << "), ";
        }
        cout << "none" << endl;
        */
        UnionFind uf(n * m);
        int j = 0;
        for (auto &idx : list) {
            int q = queries[idx];
            if (grid[0][0] >= q) continue;
            // cout << "q = " << q << endl;
            for (; j < data.size(); j++) {
                int x, y;
                idx2Pos(data[j], m, x, y);
                // cout << "j = " << j << ", x = " << x << ", y = " << y << endl;
                if (grid[x][y] >= q) break;
                for (auto &dir : dirs) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx == -1 || nx == n || ny == -1 || ny == m) continue;
                    if (grid[nx][ny] >= q) continue;
                    uf.uni(data[j], pos2Idx(nx, ny, m));
                }
            }
            ans[idx] = uf.size(0);
        }
        return ans;
    }
};