2201. Count Artifacts That Can Be Extracted

發表於 | 分類於

problem

solution

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
class Solution {
public:
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        
        vector<vector<int>> map(n, vector<int>(n,0));
        int m = artifacts.size();
        vector<int> area(m+1,0);
        for(int i=0, j = 1;i<m;++i, j++){
            for(int x = artifacts[i][0];x<=artifacts[i][2] ; x++){
                for(int y = artifacts[i][1];y<=artifacts[i][3] ;y++) map[x][y] = j;
            }
            area[j] = (artifacts[i][3]-artifacts[i][1]+1)*(artifacts[i][2]-artifacts[i][0]+1);
        }
        for(auto d :dig){
            int i=d[0], j = d[1];
            int color = map[i][j];
            
            area[color]-=1;
            
        }
        int count = 0;
        for(int i=1;i<m+1;++i){
            count+=(area[i]==0);
        }
        return count;
        
    }
};

analysis

  • time complexity O(m*n*n)
  • space complexity O(n*n)