{"id":4676,"date":"2019-01-20T09:21:28","date_gmt":"2019-01-20T17:21:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4676"},"modified":"2019-12-06T09:37:13","modified_gmt":"2019-12-06T17:37:13","slug":"leetcode-980-unique-paths-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-980-unique-paths-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 980. Unique Paths III"},"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 980. Unique Paths III - \u5237\u9898\u627e\u5de5\u4f5c EP242\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/dSXtmaGr4Fc?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>On a 2-dimensional&nbsp;<code>grid<\/code>, there are 4 types of squares:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1<\/code>&nbsp;represents the starting square.&nbsp; There is exactly one starting square.<\/li><li><code>2<\/code>&nbsp;represents the ending square.&nbsp; There is exactly one ending square.<\/li><li><code>0<\/code>&nbsp;represents empty squares we can walk over.<\/li><li><code>-1<\/code>&nbsp;represents obstacles that we cannot walk over.<\/li><\/ul>\n\n\n\n<p>Return the number of 4-directional walks&nbsp;from the starting square to the ending square, that&nbsp;<strong>walk over every non-obstacle square&nbsp;exactly once<\/strong>.<\/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>[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]\n<strong>Output: <\/strong>2\n<strong>Explanation: <\/strong>We have the following two paths: \n1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)\n2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[[1,0,0,0],[0,0,0,0],[0,0,0,2]]\n<strong>Output: <\/strong>4\n<strong>Explanation: <\/strong>We have the following four paths: \n1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)\n2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)\n3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)\n4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[[0,1],[2,0]]\n<strong>Output: <\/strong>0\n<strong>Explanation: <\/strong>\nThere is no path that walks over every empty square exactly once.\nNote that the starting and ending square can be anywhere in the grid.\n<\/pre>\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;= 20<\/code><\/li><\/ol>\n\n\n\n<p>count how many empty blocks there are and try all possible paths to end point and check whether we visited every empty blocks or not.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution:&nbsp;Brute force \/ DP<\/strong><\/h2>\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\/2019\/01\/980-ep242.png\" alt=\"\" class=\"wp-image-4681\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/980-ep242.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/980-ep242-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/980-ep242-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++\/DFS<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int uniquePathsIII(vector<vector<int>>& grid) {    \n    int sx = -1;\n    int sy = -1;\n    int n = 1;\n    for (int i = 0; i < grid.size(); ++i)\n      for (int j = 0; j < grid[0].size(); ++j)\n        if (grid[i][j] == 0) ++n;\n        else if (grid[i][j] == 1) { sx = j; sy = i; }    \n    return dfs(grid, sx, sy, n);\n  }\nprivate:\n  int dfs(vector<vector<int>>& grid, int x, int y, int n) {\n    if (x < 0 || x == grid[0].size() || \n        y < 0 || y == grid.size() || \n        grid[y][x] == -1) return 0;\n    if (grid[y][x] == 2) return n == 0;    \n    grid[y][x] = -1;\n    int paths = dfs(grid, x + 1, y, n - 1) + \n                dfs(grid, x - 1, y, n - 1) +\n                dfs(grid, x, y + 1, n - 1) + \n                dfs(grid, x, y - 1, n - 1);\n    grid[y][x] = 0;\n    return paths;\n  };\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/DP<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int uniquePathsIII(vector<vector<int>>& grid) {\n    const int n = grid.size();\n    const int m = grid[0].size();\n    const vector<int> dirs{-1, 0, 1, 0, -1};\n    \n    vector<vector<vector<short>>> cache(n, vector<vector<short>>(m, vector<short>(1 << n * m, -1)));\n    int sx = -1;\n    int sy = -1;\n    int state = 0;\n    \n    auto key = [m](int x, int y) { return 1 << (y * m + x); };\n    \n    function<short(int, int, int)> dfs = [&](int x, int y, int state) {    \n      if (cache[y][x][state] != -1) return cache[y][x][state];\n      if (grid[y][x] == 2) return static_cast<short>(state == 0); \n      int paths = 0;      \n      for (int i = 0; i < 4; ++i) {\n        const int tx = x + dirs[i];\n        const int ty = y + dirs[i + 1];\n        if (tx < 0 || tx == m || ty < 0 || ty == n || grid[ty][tx] == -1) continue;\n        if (!(state &#038; key(tx, ty))) continue;\n        paths += dfs(tx, ty, state ^ key(tx, ty));\n      }\n      return cache[y][x][state] = paths;\n    };\n    \n    for (int y = 0; y < n; ++y)\n      for (int x = 0; x < m; ++x)\n        if (grid[y][x] == 0 || grid[y][x] == 2) state |= key(x, y);\n        else if (grid[y][x] == 1) { sx = x; sy = y; }\n    return dfs(sx, sy, state);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>On a 2-dimensional&nbsp;grid, there are 4 types of squares: 1&nbsp;represents the starting square.&nbsp; There is exactly one starting square. 2&nbsp;represents the ending square.&nbsp; There is&#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":[33,437,217],"class_list":["post-4676","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-hamiltonian-path","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4676","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=4676"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4676\/revisions"}],"predecessor-version":[{"id":5924,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4676\/revisions\/5924"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4676"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4676"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4676"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}