Leetcode 2201 - Count Artifacts That Can Be Extracted

題目

Problem#

題目給你一個 n x n 的 grid 並給你一堆寶藏的地點 artifact[i] = [r1_i, c1_i, r2_i, c2_i] 其中 (r1, c1) 與 (r2, c2) 代表寶藏的左上到右下
接著給你挖掘的座標 dig[i] = [r_i, c_i] 問你最後挖了幾個寶藏(一個寶藏要被挖出 <=> 挖出寶藏所佔的所有格子)

想法#

• 時間複雜度: $\mathcal{O}(n^2)$
• 空間複雜度: $\mathcal{O}(n^2)$

AC Code#

Copy

using P=pair<int,int>;
#define MP make_pair
 
class Solution {
public:
    map<P, int> map2art;
    map<int, int> an;
    
    int digArtifacts(int n, vector<vector<int>>& art, vector<vector<int>>& dig)
    {
        for(int k = 0; k < art.size(); k++)
        {
            for(int i = art[k][0]; i <= art[k][2]; i++)
                for(int j = art[k][1]; j <= art[k][3]; j++)
                {
                    map2art[MP(i, j)] = k;
                    an[k]++;
                }
        }
        
        for(int i = 0; i < dig.size(); i++)
        {
            auto tmp = MP(dig[i][0], dig[i][1]);
            if(map2art.count(tmp))
            {
                an[map2art[tmp]]--;
            }
        }
               
        int ans = 0;
        for(auto && [k, v] : an)
        {
            if(v == 0)
                ans++;
        }
        return ans;
    }
};

view raw leetcode/2201.cpp delivered with ❤ by emgithub

賞析#

TODO

心得#

Weekly Contest 284 第二題