322. Chess Game
In a game of chess, you are given two binary arrays:
a binary array queen with size N, which represents the coordinates of N queens;
a binary array knight with size M, which represents the coordinates of M knights.
A queen can attack any knight chess in the same row, column and diagonal.
You are asked to return an answer array with size M, the ith element of which shows whether the ith knight can be attacked.
Example
Example:
Input: [[1,1],[2,2]]
[[3,3],[1,3],[4,5]]
Output: [true,true,false]
Explanation: The first knight can be attacked by queen 1 and 2.
The second knight can be attacked by queen 1 and 2.
The last knight can not be attacked.
Notice
1≤N,M≤10^5
The range of chess coordinates is a positive integer from 1 to 10^9
解法1： 注意主对角线可以用row-col来确定，反对角线可以用row+col来确定。
class Solution { public: /** * @param queen: queen‘coordinate * @param knight: knight‘coordinate * @return: if knight is attacked please return true，else return false */ vector<bool> isAttacked(vector<vector<int>> &queen, vector<vector<int>> &knight) { int len_q = queen.size(); int len_k = knight.size(); vector<bool> result(len_k, true); unordered_set<int> row_set; unordered_set<int> col_set; unordered_set<int> diag_set; unordered_set<int> rev_diag_set; for (int i = 0; i < len_q; ++i) { row_set.insert(queen[i][0]); col_set.insert(queen[i][1]); diag_set.insert(queen[i][0] - queen[i][1]); rev_diag_set.insert(queen[i][0] + queen[i][1]); } for (int i = 0; i < len_k; ++i) { if (row_set.find(knight[i][0]) == row_set.end() && col_set.find(knight[i][1]) == col_set.end() && diag_set.find(knight[i][0] - knight[i][1]) == diag_set.end() && rev_diag_set.find(knight[i][0] + knight[i][1]) == rev_diag_set.end()) result[i] = false; } return result; } };
