{"id":5757,"date":"2019-10-14T07:48:56","date_gmt":"2019-10-14T14:48:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5757"},"modified":"2019-10-15T00:30:40","modified_gmt":"2019-10-15T07:30:40","slug":"leetcode-1222-queens-that-can-attack-the-king","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1222-queens-that-can-attack-the-king\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1222. Queens That Can Attack the King"},"content":{"rendered":"\n<p>On an&nbsp;<strong>8&#215;8<\/strong>&nbsp;chessboard, there can be multiple Black Queens and one White King.<\/p>\n\n\n\n<p>Given an array of integer coordinates&nbsp;<code>queens<\/code>&nbsp;that represents the positions of the Black Queens, and a pair of coordinates&nbsp;<code>king<\/code>&nbsp;that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/10\/01\/untitled-diagram.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]\n<strong>Output:<\/strong> [[0,1],[1,0],[3,3]]\n<strong>Explanation:<\/strong>&nbsp; \nThe queen at [0,1] can attack the king cause they're in the same row. \nThe queen at [1,0] can attack the king cause they're in the same column. \nThe queen at [3,3] can attack the king cause they're in the same diagnal. \nThe queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1]. \nThe queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0]. \nThe queen at [2,4] can't attack the king cause it's not in the same row\/column\/diagnal as the king.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/10\/01\/untitled-diagram-1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]\n<strong>Output:<\/strong> [[2,2],[3,4],[4,4]]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/10\/01\/untitled-diagram-2.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]\n<strong>Output:<\/strong> [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= queens.length&nbsp;&lt;= 63<\/code><\/li><li><code>queens[0].length == 2<\/code><\/li><li><code>0 &lt;= queens[i][j] &lt;&nbsp;8<\/code><\/li><li><code>king.length == 2<\/code><\/li><li><code>0 &lt;= king[0], king[1] &lt; 8<\/code><\/li><li>At most one piece is allowed in a cell.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution2: Simulation<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {    \n    vector<vector<int>> b(8, vector<int>(8));\n    for (const auto& q : queens)\n      b[q[0]][q[1]] = 1;\n    vector<vector<int>> ans;\n    for (const auto& q : queens) {\n      for (int dx = -1; dx <= 1; ++dx)\n        for (int dy = -1; dy <= 1; ++dy) {\n          if (dx == 0 &#038;&#038; dy == 0) continue;\n          int x = q[1] + dx;\n          int y = q[0] + dy;\n          while (x >= 0 && y >= 0 && x < 8 &#038;&#038; y < 8 &#038;&#038; !b[y][x]) {\n            if (x == king[1] &#038;&#038; y == king[0])\n              ans.push_back(q);            \n            x += dx;\n            y += dy;\n          }\n        }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: HashTable + Binary Search<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<p>Support arbitrarily large boards, e.g. 1e9 x 1e9 with 1e6  # of queens.<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {    \n    unordered_map<int, map<int, vector<int>>> rows, cols, diag1, diag2;    \n    for (const auto& q : queens) {\n      const int x = q[1];\n      const int y = q[0];\n      rows[y][x] = q;\n      cols[x][y] = q;\n      diag1[x + y][x] = q;\n      diag2[x - y][x] = q;\n    }\n    \n    const int x = king[1];\n    const int y = king[0];\n    vector<vector<int>> ans;\n    find(rows, y, x, ans);\n    find(cols, x, y, ans);\n    find(diag1, x + y, x, ans);\n    find(diag2, x - y, x, ans);\n    return ans;\n  }\nprivate:\n  void find(const unordered_map<int, map<int, vector<int>>>& m, int idx, int key, vector<vector<int>>& ans) {    \n    if (!m.count(idx)) return;\n    const auto& d = m.at(idx);\n    auto it = d.upper_bound(key);\n    if (it != end(d))\n      ans.push_back(it->second);\n    if (it != begin(d))\n      ans.push_back(prev(it)->second);    \n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>On an&nbsp;8&#215;8&nbsp;chessboard, there can be multiple Black Queens and one White King. Given an array of integer coordinates&nbsp;queens&nbsp;that represents the positions of the Black Queens,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[52,119,82,511,177,510,179],"class_list":["post-5757","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-binary-search","tag-chess","tag-hashtable","tag-king","tag-medium","tag-queen","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5757","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5757"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5757\/revisions"}],"predecessor-version":[{"id":5760,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5757\/revisions\/5760"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5757"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5757"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5757"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}