【墨鳌】【简单题,但是要细致一点,别忘了关灯的时候把自己也关了

题目链接
题解链接

题外话

无意间在评论区发现了原来是 125周赛题
所以晚上补充一下,他山之石,可以攻玉, @bigelephant29

解题思路

  • 每一个灯(坐标),有五个属性:
  1. 行 (横坐标 x )
  2. 列 (纵坐标 y )
  3. 撇 (直线 y=x+t \(\Longrightarrow\) 记录 x-y )
  4. 捺 (直线 x+y=t \(\Longrightarrow\) 记录 x+y )
  5. 表示坐标本身的二元组 (坐标 (x,y) )
  • 前四者之一为真,即亮灯
  • 然后用哈希表存一下,这五组特性,实时维护开关灯,就OK啦

代码

#define R row               //横坐标
#define C column            //纵坐标
#define P leftDown2RightUp  //y=x+t  => x-y
#define L rightDown2leftUp  //x+y=t  => x+y
#define O onLamps           //亮着的灯的集合
class Solution {    
public:
    const vector<vector<int>>ds{{0,0},{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        unordered_map<int,int>R,C,P,L;
        set<pair<int,int>>O;
        auto shift=[&](int&x,int&y,int o){R[x]+=o,C[y]+=o,P[x-y]+=o,L[x+y]+=o;};
        for(auto&p:lamps){
            auto&x=p[0],&y=p[1];
            auto lamp=make_pair(x,y);
            if(O.count(lamp)==0)O.insert(lamp),shift(x,y,1);
        }
        vector<int>ans;
        for(auto&p:queries){
            auto&x=p[0],&y=p[1];
            ans.push_back((R[x] || C[y] || P[x-y] || L[x+y]));
            for(auto&d:ds){
                auto nx=x+d[0],ny=y+d[1];
                auto lamp=make_pair(nx,ny);
                if(O.count(lamp)>0)O.erase(lamp),shift(nx,ny,-1);
            }
        }
        return ans;
    }
};
class Solution {
public:
    unordered_map<int, int> ver, hor;
    unordered_map<int, int> d1, d2;
    set<pair<int,int>> st;
    
    void add(pair<int,int> pr) {
        ver[pr.first]++;
        hor[pr.second]++;
        d1[pr.first+pr.second]++;
        d2[pr.first-pr.second]++;
        st.insert(pr);
    }
    
    void close(pair<int,int> pr) {
        ver[pr.first]--;
        hor[pr.second]--;
        d1[pr.first+pr.second]--;
        d2[pr.first-pr.second]--;
        st.erase(pr);
    }
    
    int query(pair<int,int> pr) {
        return ver[pr.first] > 0 || hor[pr.second] > 0 || d1[pr.first+pr.second] > 0 || d2[pr.first-pr.second] > 0;
    }
    
    vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        for(auto e: lamps) {
            add(make_pair(e[0], e[1]));
        }
        vector<int> ans;
        for(auto e: queries) {
            int x = e[0], y = e[1];
            ans.push_back(query(make_pair(x,y)));
            for(int i = -1 ; i <= 1 ; i++) {
                for(int j = -1 ; j <= 1 ; j++) {
                    if(st.find(make_pair(x+i, y+j)) != st.end()) {
                        close(make_pair(x+i,y+j));
                    }
                }
            }
        }
        return ans;
    }
};
上一篇:单向环形链表与Josephu 问题


下一篇:快速排序