kmjp's blog

競技プログラミング参加記です

LeetCode Weekly Contest 125 : 1001. Grid Illumination

うーん、LeetCodeはあまり面白いと思える問題がないなぁ。
https://leetcode.com/contest/weekly-contest-125/problems/grid-illumination/

問題

2次元グリッド上にいくつかのランプがある。
各ランプはグリッドの上下左右斜めに沿って8方向を無限遠まで照らす。

セルの位置を指定するクエリが与えられるので、順次以下処理せよ。

  • そのセルが少なくとも1つ以上にランプに照らされるか答える。
  • その後、そのセルおよび周囲8バスについているランプがあれば消す。

解法

あるマスが照らされる条件は、以下のいずれかを満たす点灯ランプが1個でもあることである。

  • Y座標が一致
  • X座標が一致
  • Y座標-X座標が一致
  • Y座標+X座標が一致

よって4つのmapを用いてそれぞれ該当するランプ数をカウントすればよい。

map<int,int> Y,X,YmX,YpX;
set<pair<int,int>> S;

class Solution {
public:
	void add(int y,int x) {
		S.insert({y,x});
		Y[y]++;
		X[x]++;
		YmX[y-x]++;
		YpX[y+x]++;
	}
	void del(int y,int x) {
		if(S.count({y,x})==0) return;
		S.erase({y,x});
		Y[y]--;
		X[x]--;
		YmX[y-x]--;
		YpX[y+x]--;
	}

    vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
		S.clear();
		Y.clear();
		X.clear();
		YmX.clear();
		YpX.clear();
        
        FORR(a,lamps) add(a[1],a[0]);
        
        vector<int> R;
        FORR(q,queries) {
			int ok=Y[q[1]]+X[q[0]]+YmX[q[1]-q[0]]+YpX[q[1]+q[0]];
			R.push_back(ok>0);
			for(int y=q[1]-1;y<=q[1]+1;y++) for(int x=q[0]-1;x<=q[0]+1;x++) del(y,x);
		}
		return R;
    }
};

まとめ

これ6か7ptでもいい気がするなぁ…。