{"id":5743,"date":"2019-10-09T21:44:39","date_gmt":"2019-10-10T04:44:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5743"},"modified":"2019-10-09T22:46:14","modified_gmt":"2019-10-10T05:46:14","slug":"leetcode-130-surrounded-regions","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-130-surrounded-regions\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 130. Surrounded Regions"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 130. Surrounded Regions - \u5237\u9898\u627e\u5de5\u4f5c EP274\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/kyvGkcXs_rE?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<\/div><\/figure>\n\n\n\n<p>Given a 2D board containing&nbsp;<code>'X'<\/code>&nbsp;and&nbsp;<code>'O'<\/code>&nbsp;(<strong>the letter O<\/strong>), capture all regions surrounded by&nbsp;<code>'X'<\/code>.<\/p>\n\n\n\n<p>A region is captured by flipping all&nbsp;<code>'O'<\/code>s into&nbsp;<code>'X'<\/code>s in that surrounded region.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">X X X X\nX O O X\nX X O X\nX O X X\n<\/pre>\n\n\n\n<p>After running your function, the board should be:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">X X X X\nX X X X\nX X X X\nX O X X\n<\/pre>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>Surrounded regions shouldn\u2019t be on the border, which means that any&nbsp;<code>'O'<\/code>&nbsp;on the border of the board are not flipped to&nbsp;<code>'X'<\/code>. Any&nbsp;<code>'O'<\/code>&nbsp;that is not on the border and it is not connected to an&nbsp;<code>'O'<\/code>&nbsp;on the border will be flipped to&nbsp;<code>'X'<\/code>. Two cells are connected if they are adjacent cells connected horizontally or vertically.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(m*n)<br>Space complexity: O(m*n)<\/p>\n\n\n\n<p>Only starts DFS at border cells of O.<\/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  void solve(vector<vector<char>>& board) {\n    const int m = board.size();\n    if (m == 0) return;\n    const int n = board[0].size();    \n    \n    function<void(int, int)> dfs = [&](int x, int y) {\n      if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') return;\n      board[y][x] = 'G'; \/\/ mark it as good      \n      dfs(x - 1, y);\n      dfs(x + 1, y);\n      dfs(x, y - 1);\n      dfs(x, y + 1);\n    };\n    \n    for (int y = 0; y < m; ++y)\n      dfs(0, y), dfs(n - 1, y);    \n    \n    for (int x = 0; x < n; ++x)\n      dfs(x, 0), dfs(x, m - 1);    \n    \n    map<char, char> v{{'G','O'},{'O','X'}, {'X','X'}};\n    for (int y = 0; y < m; ++y)\n      for (int x = 0; x < n; ++x)\n        board[y][x] = v[board[y][x]];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a 2D board containing&nbsp;&#8216;X&#8217;&nbsp;and&nbsp;&#8216;O&#8217;&nbsp;(the letter O), capture all regions surrounded by&nbsp;&#8216;X&#8217;. A region is captured by flipping all&nbsp;&#8216;O&#8217;s into&nbsp;&#8216;X&#8217;s in that surrounded region. Example:&#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],"tags":[7,33,177,366],"class_list":["post-5743","post","type-post","status-publish","format-standard","hentry","category-searching","tag-board","tag-dfs","tag-medium","tag-omn","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5743","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=5743"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5743\/revisions"}],"predecessor-version":[{"id":5747,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5743\/revisions\/5747"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5743"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5743"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5743"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}