Leetcode-1001 Grid Illumination(网格照明)

作者水平有限，所发仅为个人愚见，如有明显谬误，望斧正

先考虑使用暴力/模拟，观察所给数据范围，N最高可达10⁹，因此模拟必定不可行。观察询问队列的长度和灯队列的长度，因为询问队列一定要遍历一遍，所以由此可想到O(nm)解法(其中n为询问队列长度，m为灯队列长度)，即在遍历询问队列的同时，遍历灯队列，如果询问队列的询问点被灯照亮，则在结果数组的相应位置将值置为1，否则为0。当一个询问点结束以后，将此询问点周围的灯熄灭，即从灯队列中删除。

 1 #define pb push_back
 2 #define maxSize 3939
 3 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 4 
 5 class Solution
 6 {
 7     public:
 8         bool ispang(int x1,int y1,int x2,int y2)
 9         {
10             return (x1==y1&&x2==y2)
11             || (x1==x2&&x2==y2-1)
12             || (x1==x2&&x2==y2+1)
13             || (x1==x2-1&&x2==y2)
14             || (x1==x2-1&&x2==y2-1)
15             || (x1==x2-1&&x2==y2+1)
16             || (x1==x2+1&&x2==y2)
17             || (x1==x2+1&&x2==y2-1)
18             || (x1==x2+1&&x2==y2+1);
19         }
20         vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries)
21         {
22             int qsz = queries.size();
23             int lsz = lamps.size();
24             set<pair<int,int>> lamp;
25             for(int i = 0;i < lsz;i ++)
26                 lamp.insert({lamps[i][0],lamps[i][1]});
27             
28             vector<int> rnt(qsz,0);
29             
30             for(int i = 0;i < qsz;i ++)
31             {
32                 for(auto j = lamp.begin();j != lamp.end();j ++)
33                 {
34                     if(queries[i][0]==j->first||queries[i][1]==j->second
35                     ||abs(queries[i][0]-j->first)==abs(queries[i][1]-j->second))
36                     {
37                         rnt[i] = 1;
38                         break;
39                     }
40                 }
41                 
42                 for(auto j = lamp.begin();j != lamp.end();j ++)
43                 {
44                     if(ispang(queries[i][0],queries[i][1],j->first,j->second))
45                     {
46                         lamp.erase(j);
47                         break;
48                     }
49                 }
50             }
51             return rnt;
52         }
53 };

Leetcode-1001(C++)(32/33通过样例)

那么很显然，在最大数据量情况下，加上常数，需要数十秒左右才能跑完，因此超时。寻求时间复杂度更低的解法，对原程序进行优化。

但由此我们观察到有以下两点是必须完成的动作：

① 对给出询问点的询问操作

② 对询问点周围灯的删除操作

对于②删除操作，可以将pari<int,int>的点对作为set的查询元素，则可以方便的将灯从灯队列中加入或删除，也就是对于删除操作，时间复杂度可以将为O(nlogm)。于是考虑对①询问操作的优化，若将询问操作的时间复杂度也将为O(nlogm)，则问题可解。

查询分为四条：

①行的查询

②列的查询

③主对角线查询

④辅对角线查询

观察到若查询点与灯有同一x,则行相同

若查询点与灯有同一y,则列相同

若查询点与灯有同一x-y,则在同一主对角线

若查询点与灯有同一x+y,则在同一辅对角线

对灯队列进行预处理，对于每一行，每一列，每一主对角线，每一辅对角线，分别计算有多少个灯在其上，删除时，每删除一个灯，将其照亮区域的相对应行列对角线的灯数量减一，这样查询时如果对于某一行或列或者对角线有灯在其上，也就是这四个查询数组的值只要有一个不为0，则该点一定是被照亮的。由此，题目解决。

 1 #define pb push_back
 2 #define maxSize 3939
 3 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 4 
 5 int dx[] = {0,1,-1,0,1,-1,0,1,-1};
 6 int dy[] = {-1,-1,-1,0,0,0,1,1,1};
 7 class Solution
 8 {
 9     public:
10         set<pair<int,int>> s;
11         map<int,int> cm,rm,dxm,dym;
12         void add(int x,int y)
13         {
14             s.insert({x,y});
15             cm[x] ++;
16             rm[y] ++;
17             dxm[x+y] ++;
18             dym[x-y] ++;
19         }
20         void remove(int x,int y)
21         {
22             auto it = s.find({x,y});
23             if(it==s.end())
24                 return ;
25             s.erase(it);
26             cm[x] --;
27             rm[y] --;
28             dxm[x+y] --;
29             dym[x-y] --;
30         }
31         int judge(int x,int y)
32         {
33             return cm[x]>0||rm[y]>0||dxm[x+y]>0||dym[x-y];
34         }
35         vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries)
36         {
37             _for(i,0,lamps.size())
38                 add(lamps[i][0],lamps[i][1]);
39             
40             vector<int> rnt;
41             _for(i,0,queries.size())
42             {
43                 rnt.push_back(judge(queries[i][0],queries[i][1]));
44                 _for(j,0,9)
45                 {
46                     int nx = queries[i][0]+dx[j];
47                     int ny = queries[i][1]+dy[j];
48                     remove(nx,ny);
49                 }
50             }
51             return rnt;
52         }
53 };

Leetcode-1001(C++)

执行用时:1200ms