{"id":2206,"date":"2018-03-18T02:43:17","date_gmt":"2018-03-18T09:43:17","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2206"},"modified":"2018-09-03T21:37:32","modified_gmt":"2018-09-04T04:37:32","slug":"leetcode-803-bricks-falling-when-hit","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-803-bricks-falling-when-hit\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 803. Bricks Falling When Hit"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 803. Bricks Falling When Hit - \u5237\u9898\u627e\u5de5\u4f5c EP175\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/UrMZrAyyliw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u5835\u7816\u5899\uff0c\u6c42\u6bcf\u6b21\u51fb\u788e\u4e00\u5757\u540e\u6389\u843d\u7684\u7816\u5934\u6570\u91cf\u3002<\/p>\n<p>We have a grid of 1s and 0s; the 1s in a cell represent bricks.\u00a0 A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.<\/p>\n<p>We will do some erasures\u00a0sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may\u00a0drop because of that\u00a0erasure.<\/p>\n<p>Return an array representing the number of bricks that will drop after each erasure in sequence.<\/p>\n<pre class=\"crayon:false\"><strong>Example 1:<\/strong>\r\n<strong>Input:<\/strong> \r\ngrid = [[1,0,0,0],[1,1,1,0]]\r\nhits = [[1,0]]\r\n<strong>Output:<\/strong> [2]\r\n<strong>Explanation: <\/strong>\r\nIf we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.<\/pre>\n<pre class=\"crayon:false\"><strong>Example 2:<\/strong>\r\n<strong>Input:<\/strong> \r\ngrid = [[1,0,0,0],[1,1,0,0]]\r\nhits = [[1,1],[1,0]]\r\n<strong>Output:<\/strong> [0,0]\r\n<strong>Explanation: <\/strong>\r\nWhen we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping.  Note that the erased brick (1, 0) will not be counted as a dropped brick.<\/pre>\n<h1>Idea<\/h1>\n<ol>\n<li>For each day, hit and clear the specified brick.<\/li>\n<li>Find all connected components (CCs) using DFS.<\/li>\n<li>For each CC, if there is no brick that is on the first row that the entire cc will drop. Clear those CCs.<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2223\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/803-ep175.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/803-ep175.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/803-ep175-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/803-ep175-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1>Solution: DFS<\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 1261 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; hitBricks(vector&lt;vector&lt;int&gt;&gt;&amp; grid, vector&lt;vector&lt;int&gt;&gt;&amp; hits) {    \r\n    dirs_ = {0, -1, 0, 1, 0};    \r\n    m_ = grid.size();\r\n    n_ = grid[0].size();\r\n    g_.swap(grid);\r\n    seq_ = 1;\r\n    \r\n    vector&lt;int&gt; ans;\r\n    for (int i = 0; i &lt; hits.size(); ++i)\r\n      ans.push_back(hit(hits[i][1], hits[i][0]));\r\n    return ans;\r\n  }\r\nprivate:\r\n  vector&lt;vector&lt;int&gt;&gt; g_;\r\n  vector&lt;int&gt; dirs_;\r\n  int seq_;\r\n  int m_;\r\n  int n_;\r\n  \r\n  \/\/ hit x, y and return the number of bricks fallen.\r\n  int hit(int x, int y) {\r\n    if (x &lt; 0 || x &gt;= n_ || y &lt; 0 || y &gt;= m_) return 0;    \r\n    g_[y][x] = 0;\r\n    int ans = 0; \r\n    for (int i = 0; i &lt; 4; ++i) {\r\n      ++seq_;\r\n      int count = 0;\r\n      if (!fall(x + dirs_[i], y + dirs_[i + 1], false, count)) continue;      \r\n      ++seq_;\r\n      ans += count;\r\n      fall(x + dirs_[i], y + dirs_[i + 1], true, count);\r\n    }\r\n    return ans;\r\n  }\r\n  \r\n  \/\/ Check whether the CC contains (x, y) will fall or not.\r\n  \/\/ Set all nodes in this CC as seq_ or 0 if clear.\r\n  \/\/ count: the # of nodes in this CC.\r\n  bool fall(int x, int y, bool clear, int&amp; count) {\r\n    if (x &lt; 0 || x &gt;= n_ || y &lt; 0 || y &gt;= m_) return true;\r\n    if (g_[y][x] == seq_ || g_[y][x] == 0) return true;\r\n    if (y == 0) return false;\r\n    g_[y][x] = clear ? 0 : seq_;\r\n    ++count;\r\n    for (int i = 0; i &lt; 4; ++i)\r\n      if (!fall(x + dirs_[i], y + dirs_[i + 1], clear, count)) return false;\r\n    return true;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Stack Overflow (1024 recursive calls)\r\nclass Solution {\r\n  int[] dirs = new int[]{0, -1, 0, 1, 0};\r\n  int m;\r\n  int n;\r\n  int[][] g;\r\n  int seq;\r\n  int count;\r\n  \r\n  public int[] hitBricks(int[][] grid, int[][] hits) {\r\n    this.g = grid;\r\n    this.m = grid.length;\r\n    this.n = grid[0].length;\r\n    \r\n    int[] ans = new int[hits.length];\r\n    \r\n    for (int i = 0; i &lt; hits.length; ++i)\r\n      ans[i] = hit(hits[i][1], hits[i][0]);\r\n    \r\n    return ans;\r\n  }\r\n  \r\n  private int hit(int x, int y) {\r\n    if (x &lt; 0 || x &gt;= n || y &lt; 0 || y &gt;= m || g[y][x] == 0) return 0;\r\n    g[y][x] = 0;\r\n    int ans = 0;\r\n    for (int i = 0; i &lt; 4; ++i) {\r\n      ++seq;      \r\n      count = 0;\r\n      if (!fall(x + dirs[i], y + dirs[i + 1], false)) continue;    \r\n      ans += count;\r\n      ++seq;\r\n      fall(x + dirs[i], y + dirs[i + 1], true);\r\n    }\r\n    return ans;\r\n  }\r\n  \r\n  private boolean fall(int x, int y, boolean clear) {\r\n    if (x &lt; 0 || x &gt;= n || y &lt; 0 || y &gt;= m) return true;\r\n    if (g[y][x] == seq || g[y][x] == 0) return true;\r\n    if (y == 0) return false;\r\n    g[y][x] = clear ? 0 : seq;\r\n    ++count;\r\n    for (int i = 0; i &lt; 4; ++i)\r\n      if (!fall(x + dirs[i], y + dirs[i + 1], clear)) return false;\r\n    return true;\r\n  }\r\n}<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-749-contain-virus\/\">\u82b1\u82b1\u9171 LeetCode 749. Contain Virus<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u5835\u7816\u5899\uff0c\u6c42\u6bcf\u6b21\u51fb\u788e\u4e00\u5757\u540e\u6389\u843d\u7684\u7816\u5934\u6570\u91cf\u3002 We have a grid of 1s and 0s; the 1s in a cell represent bricks.\u00a0 A brick will not drop if and only&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44,48],"tags":[102,33,217,42,179],"class_list":["post-2206","post","type-post","status-publish","format-standard","hentry","category-searching","category-simulation","tag-connected-components","tag-dfs","tag-hard","tag-search","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2206","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=2206"}],"version-history":[{"count":12,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2206\/revisions"}],"predecessor-version":[{"id":3836,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2206\/revisions\/3836"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2206"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2206"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2206"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}