[leetcode]Grid Illumination
11003 ワード
注意事項
戻り値
lampGrid[dy].erase(dx)
lampGrid[y].insert(x).second
ハッシュ表
に答える
N-Queensの問題と同じです.hashテーブルを使用するだけです.さもないとTLEを食べます.
コード#コード#
C++
class Solution {
private:
unordered_map <int,int> cols, rows, leftDiag, rightDiag;
unordered_map <int,unordered_set<int>> lampGrid;
int d[3] = {-1,0,1};
public:
vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
vector<int> ans;
for(int i = 0; i < lamps.size(); i++){
int y = lamps[i][0];
int x = lamps[i][1];
if(lampGrid[y].insert(x).second){
cols[x]++;
rows[y]++;
leftDiag[y-x]++;
rightDiag[y+x]++;
}
}
for(int i = 0; i <queries.size(); i++){
int y = queries[i][0];
int x = queries[i][1];
int _ = cols[x]||rows[y]||leftDiag[y-x]||rightDiag[y+x] ? 1 : 0;
//꺼져있으면 켜져있는 램프가 근처에 있을 확률 0%
if(_){
for(int j = 0; j < 9; j++){
int dy = y + d[j/3];
int dx = x + d[j%3];
if(lampGrid[dy].erase(dx)){
cols[dx]--;
rows[dy]--;
leftDiag[dy-dx]--;
rightDiag[dy+dx]--;
}
}
}
ans.push_back(_);
}
return ans;
}
};
Reference
この問題について([leetcode]Grid Illumination), 我々は、より多くの情報をここで見つけました https://velog.io/@6047198844/leetcodeGrid-Illuminationテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol