{"id":9710,"date":"2022-05-01T22:37:13","date_gmt":"2022-05-02T05:37:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9710"},"modified":"2022-05-01T22:44:46","modified_gmt":"2022-05-02T05:44:46","slug":"leetcode-2257-count-unguarded-cells-in-the-grid","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-2257-count-unguarded-cells-in-the-grid\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2257. Count Unguarded Cells in the Grid"},"content":{"rendered":"\n

You are given two integers m<\/code> and n<\/code> representing a 0-indexed<\/strong> m x n<\/code> grid. You are also given two 2D integer arrays guards<\/code> and walls<\/code> where guards[i] = [rowi<\/sub>, coli<\/sub>]<\/code> and walls[j] = [rowj<\/sub>, colj<\/sub>]<\/code> represent the positions of the ith<\/sup><\/code> guard and jth<\/sup><\/code> wall respectively.<\/p>\n\n\n\n

A guard can see every<\/strong> cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed<\/strong> by a wall or another guard. A cell is guarded<\/strong> if there is at least<\/strong> one guard that can see it.<\/p>\n\n\n\n

Return the number of unoccupied cells that are not<\/strong> guarded<\/strong>.<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]\nOutput:<\/strong> 7\nExplanation:<\/strong> The guarded and unguarded cells are shown in red and green respectively in the above diagram.\nThere are a total of 7 unguarded cells, so we return 7.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]\nOutput:<\/strong> 4\nExplanation:<\/strong> The unguarded cells are shown in green in the above diagram.\nThere are a total of 4 unguarded cells, so we return 4.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= m, n <= 105<\/sup><\/code><\/li>
  • 2 <= m * n <= 105<\/sup><\/code><\/li>
  • 1 <= guards.length, walls.length <= 5 * 104<\/sup><\/code><\/li>
  • 2 <= guards.length + walls.length <= m * n<\/code><\/li>
  • guards[i].length == walls[j].length == 2<\/code><\/li>
  • 0 <= rowi<\/sub>, rowj<\/sub> < m<\/code><\/li>
  • 0 <= coli<\/sub>, colj<\/sub> < n<\/code><\/li>
  • All the positions in guards<\/code> and walls<\/code> are unique<\/strong>.<\/li><\/ul>\n\n\n\n
    Solution: Simulation<\/strong><\/h2>\n\n\n\n
    Enumerate each cell, for each guard, shoot rays to 4 directions, mark cells on the way to 1 and stop when hit a guard or a wall. <\/p>\n\n\n\n
    Time complexity: O(mn)
    Space complexity: O(mn)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countUnguarded(int m, int n, vector>& guards, vector>& walls) {\n    vector> s(m, vector(n));\n    for (const auto& g : guards)\n      s[g[0]][g[1]] = 2;\n    \n    for (const auto& w : walls)\n      s[w[0]][w[1]] = 3;\n    \n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j) {\n        if (s[i][j] != 2) continue;\n        for (int y = i - 1; y >= 0; s[y--][j] = 1)\n          if (s[y][j] >= 2) break;          \n        for (int y = i + 1; y < m; s[y++][j] = 1)\n          if (s[y][j] >= 2) break;        \n        for (int x = j - 1; x >= 0; s[i][x--] = 1)\n          if (s[i][x] >= 2) break;    \n        for (int x = j + 1; x < n; s[i][x++] = 1)\n          if (s[i][x] >= 2) break;          \n      }    \n    int ans = 0;\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j)\n        ans += !s[i][j];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [rowi, coli] and walls[j] = [rowj, colj] represent the positions of…<\/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":[278,177,179],"class_list":["post-9710","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-grid","tag-medium","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9710","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=9710"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9710\/revisions"}],"predecessor-version":[{"id":9713,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9710\/revisions\/9713"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9710"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9710"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9710"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}