{"id":4484,"date":"2018-12-18T19:08:57","date_gmt":"2018-12-19T03:08:57","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4484"},"modified":"2018-12-21T09:36:39","modified_gmt":"2018-12-21T17:36:39","slug":"leetcode-959-regions-cut-by-slashes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-959-regions-cut-by-slashes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 959. Regions Cut By Slashes"},"content":{"rendered":"\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 959. Regions Cut By Slashes - \u5237\u9898\u627e\u5de5\u4f5c EP235\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/n3s9Q7GtfB4?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>\n\n\n\n<p>In a N x N&nbsp;<code>grid<\/code>&nbsp;composed of 1 x 1 squares, each 1 x 1 square consists of a&nbsp;<code>\/<\/code>,&nbsp;<code>\\<\/code>, or blank space.&nbsp; These characters divide the square into contiguous regions.<\/p>\n\n\n\n<p>(Note that backslash characters are escaped, so a&nbsp;<code>\\<\/code>&nbsp;is represented as&nbsp;<code>\"\\\\\"<\/code>.)<\/p>\n\n\n\n<p>Return the number of regions.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:<\/strong>[&nbsp; \" \/\",&nbsp; \"\/ \"]<br><strong>Output: <\/strong>2<br><strong>Explanation: <\/strong>The 2x2 grid is as follows:<\/pre>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/12\/15\/1.png\">\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:<\/strong>[&nbsp; \" \/\",&nbsp; \"  \"]<br><strong>Output: <\/strong>1<br><strong>Explanation: <\/strong>The 2x2 grid is as follows:<\/pre>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/12\/15\/2.png\">\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:<\/strong>[&nbsp; \"\\\\\/\",&nbsp; \"\/\\\\\"]<br><strong>Output: <\/strong>4<br><strong>Explanation: <\/strong>(Recall that because \\ characters are escaped, \"\\\\\/\" refers to \\\/, and \"\/\\\\\" refers to \/\\.)The 2x2 grid is as follows:<\/pre>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/12\/15\/3.png\">\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:<\/strong>[&nbsp; \"\/\\\\\",&nbsp; \"\\\\\/\"]<br><strong>Output: <\/strong>5<br><strong>Explanation: <\/strong>(Recall that because \\ characters are escaped, \"\/\\\\\" refers to \/\\, and \"\\\\\/\" refers to \\\/.)The 2x2 grid is as follows:<\/pre>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/12\/15\/4.png\">\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:<\/strong>[&nbsp; \"\/\/\",&nbsp; \"\/ \"]<br><strong>Output: <\/strong>3<br><strong>Explanation: <\/strong>The 2x2 grid is as follows:<\/pre>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/12\/15\/5.png\">\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>1 &lt;= grid.length == grid[0].length &lt;= 30<\/code><\/li><li><code>grid[i][j]<\/code>&nbsp;is either&nbsp;<code>'\/'<\/code>,&nbsp;<code>'\\'<\/code>, or&nbsp;<code>' '<\/code>.<\/li><\/ol>\n\n\n\n<h1 class=\"wp-block-heading\"><strong>Solution 1: Split grid into 4 triangles and Union Find Faces<\/strong><\/h1>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-1.png\" alt=\"\" class=\"wp-image-4496\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Divide each grid into 4 triangles and union them if not split.<br>Time complexity: O(n^2*alphn(n^2))<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\nclass Solution {  \npublic:\n  int regionsBySlashes(vector<string>& grid) {\n    int n = grid.size();    \n    DSU dsu(4 * n * n);\n    for (int r = 0; r < n; ++r)\n      for (int c = 0; c < n; ++c) {\n        int index = 4 * (r * n + c);\n        switch (grid[r][c]) {\n          case '\/':\n            dsu.merge(index + 0, index + 3);\n            dsu.merge(index + 1, index + 2);\n            break;\n          case '\\\\':\n            dsu.merge(index + 0, index + 1);\n            dsu.merge(index + 2, index + 3);\n            break;\n          case ' ':\n            dsu.merge(index + 0, index + 1);\n            dsu.merge(index + 1, index + 2);\n            dsu.merge(index + 2, index + 3);\n            break;\n          default: break;\n        }\n        if (r + 1 < n)\n          dsu.merge(index + 2, index + 4 * n + 0);\n        if (c + 1 < n)\n          dsu.merge(index + 1, index + 4 + 3);\n      }\n    int ans = 0;\n    for (int i = 0; i < 4 * n * n; ++i)\n      if (dsu.find(i) == i) ++ans;\n    return ans;\n  }\nprivate:\n  class DSU {\n    public:\n      DSU(int n): parent_(n) {\n        for (int i = 0; i < n; ++i)\n          parent_[i] = i;\n      }\n      \n      int find(int x) {\n        if (parent_[x] != x) parent_[x] = find(parent_[x]);\n        return parent_[x];\n      }\n      \n      void merge(int x, int y) {\n        parent_[find(x)] = find(y);\n      }\n    private:\n      vector<int> parent_;\n  };\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h1 class=\"wp-block-heading\"><br><strong>Solution 2: Euler&#8217;s Formula \/ Union-Find vertices<\/strong><\/h1>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-2.png\" alt=\"\" class=\"wp-image-4497\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\nclass Solution {  \npublic:\n  int regionsBySlashes(vector<string>& grid) {\n    int n = grid.size();\n    p_ = vector<int>((n + 1) * (n + 1));     \n    \/\/ All vertices on the boundaries are merged into root(0).    \n    for (int r = 0; r < n + 1; ++r)\n      for (int c = 0; c < n + 1; ++c)\n        p_[getIndex(n, r, c)] = (r == 0 || r == n || c == 0 || c == n) ? 0 : getIndex(n, r, c);\n    \n    int f = 1;    \n    for (int r = 0; r < n; ++r)\n      for (int c = 0; c < n; ++c) {\n        if (grid[r][c] == ' ') continue;\n        \/\/ A new face will created if two vertices are already in the same group.        \n        if (grid[r][c] == '\/') {\n          f += merge(getIndex(n, r, c + 1),\n                     getIndex(n, r + 1, c));\n        } else {\n          f += merge(getIndex(n, r, c),\n                     getIndex(n, r + 1, c + 1));\n        }\n      }    \n    return f;\n  }\nprivate:\n  vector<int> p_;  \n  \n  int getIndex(int n, int r, int c) { return r * (n + 1) + c; }  \n      \n  int find(int x) {\n    if (p_[x] != x) p_[x] = find(p_[x]);\n      return p_[x];\n  }\n  \n  int merge(int x, int y) {\n    int rx = find(x);\n    int ry = find(y);\n    if (rx == ry) return 1;\n    p_[ry] = rx;\n    return 0;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h1 class=\"wp-block-heading\" id=\"mce_0\"><strong>Solution 3: Pixelation (Upscale 3 times) <\/strong><\/h1>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-3.png\" alt=\"\" class=\"wp-image-4519\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/12\/959-ep235-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n\/\/ Author: Huahua, running time: 20 ms\nclass Solution {\npublic:\n  int regionsBySlashes(vector<string>& grid) {\n    const int n = grid.size();\n    vector<vector<int>> g(n * 3, vector<int>(n * 3));\n    for (int i = 0; i < n; ++i)\n      for (int j = 0; j < n; ++j) {\n        if (grid[i][j] == '\/') {\n          g[i * 3 + 0][j * 3 + 2] = 1;\n          g[i * 3 + 1][j * 3 + 1] = 1;\n          g[i * 3 + 2][j * 3 + 0] = 1;\n        } else if (grid[i][j] == '\\\\') {\n          g[i * 3 + 0][j * 3 + 0] = 1;\n          g[i * 3 + 1][j * 3 + 1] = 1;\n          g[i * 3 + 2][j * 3 + 2] = 1;\n        }\n      }\n    int ans = 0;\n    for (int i = 0; i < 3 * n; ++i)\n      for (int j = 0; j < 3 * n; ++j) {\n        if (g[i][j]) continue;\n        visit(g, j, i, n * 3);\n        ++ans;\n      }\n    return ans;\n  }\nprivate:\n  void visit(vector<vector<int>>& g, int x, int y, int n) {\n    if (x < 0 || x >= n || y < 0 || y >= n) return;\n    if (g[y][x]) return;\n    g[y][x] = 1;\n    visit(g, x + 1, y, n);\n    visit(g, x, y + 1, n);\n    visit(g, x - 1, y, n);\n    visit(g, x, y - 1, n);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>In a N x N&nbsp;grid&nbsp;composed of 1 x 1 squares, each 1 x 1 square consists of a&nbsp;\/,&nbsp;\\, or blank space.&nbsp; These characters divide the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[284,77,177,129,113],"class_list":["post-4484","post","type-post","status-publish","format-standard","hentry","category-graph","tag-geometry","tag-graph","tag-medium","tag-merge","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4484","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=4484"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4484\/revisions"}],"predecessor-version":[{"id":4520,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4484\/revisions\/4520"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4484"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4484"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}