{"id":4750,"date":"2019-01-31T20:46:57","date_gmt":"2019-02-01T04:46:57","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4750"},"modified":"2019-01-31T23:14:34","modified_gmt":"2019-02-01T07:14:34","slug":"leetcode-778-swim-in-rising-water","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/heap\/leetcode-778-swim-in-rising-water\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 778. Swim in Rising Water"},"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 778. Swim in Rising Water - \u5237\u9898\u627e\u5de5\u4f5c EP244\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/umdk98ynLSY?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 an N x N&nbsp;<code>grid<\/code>, each square&nbsp;<code>grid[i][j]<\/code>&nbsp;represents the elevation at that point&nbsp;<code>(i,j)<\/code>.<\/p>\n\n\n\n<p>Now rain starts to fall. At time&nbsp;<code>t<\/code>, the depth of the water everywhere is&nbsp;<code>t<\/code>. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are&nbsp;at most&nbsp;<code>t<\/code>. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.<\/p>\n\n\n\n<p>You start at the top left square&nbsp;<code>(0, 0)<\/code>. What is the least time until you can reach the bottom right square&nbsp;<code>(N-1, N-1)<\/code>?<\/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> [[0,2],[1,3]]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong>\nAt time <code>0<\/code>, you are in grid location <code>(0, 0)<\/code>.\nYou cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.\n\nYou cannot reach point <code>(1, 1)<\/code> until time <code>3<\/code>.\nWhen the depth of water is <code>3<\/code>, we can swim anywhere inside the grid.\n<\/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> [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]\n<strong>Output:<\/strong> 16\n<strong>Explanation:<\/strong>\n<strong> 0  1  2  3  4<\/strong>\n24 23 22 21  <strong>5<\/strong>\n<strong>12 13 14 15 16<\/strong>\n<strong>11<\/strong> 17 18 19 20\n<strong>10  9  8  7  6<\/strong>\n\nThe final route is marked in bold.\nWe need to wait until time 16 so that (0, 0) and (4, 4) are connected.\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>2 &lt;= N &lt;= 50<\/code>.<\/li><li>grid[i][j] is a permutation of [0, &#8230;, N*N &#8211; 1].<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Dijkstra&#8217;s\u00a0Algorithm<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n^2*logn)<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 lang=\"c++\">\n\/\/ Author: Huahua, running time: 8 ms\nclass Solution {\npublic:\n  int swimInWater(vector<vector<int>>& grid) {\n    const int n = grid.size();\n    priority_queue<pair<int, int>> q; \/\/ {-time, y * N + x}\n    q.push({-grid[0][0], 0 * n + 0});\n    vector<int> seen(n * n);\n    vector<int> dirs{-1, 0, 1, 0, -1};\n    seen[0 * n + 0] = 1;\n    while (!q.empty()) {\n      auto node = q.top(); q.pop();\n      int t = -node.first;\n      int x = node.second % n;\n      int y = node.second \/ n;      \n      if (x == n - 1 && y == n - 1) return t;\n      for (int i = 0; i < 4; ++i) {\n        int tx = x + dirs[i];\n        int ty = y + dirs[i + 1];\n        if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;\n        if (seen[ty * n + tx]) continue;\n        seen[ty * n + tx] = 1;\n        q.push({-max(t, grid[ty][tx]), ty * n + tx});\n      }\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Binary Search\u00a0+\u00a0BFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(2logn * 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 lang=\"c++\">\n\/\/ Author: Huahua, running time: 8 ms\nclass Solution {\npublic:\n  int swimInWater(vector<vector<int>>& grid) {\n    const int n = grid.size();\n    auto hasPath = [&grid, n](int t) {\n      if (grid[0][0] > t) return false;      \n      queue<int> q;\n      vector<int> seen(n * n);\n      vector<int> dirs{1, 0, -1, 0, 1};\n      q.push(0);\n      \n      while (!q.empty()) {\n        const int x = q.front() % n;\n        const int y = q.front() \/ n;\n        q.pop();\n        if (x == n - 1 && y == n - 1) return true;\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 || ty < 0 || tx >= n || ty >= n || grid[ty][tx] > t) continue;\n          const int key = ty * n + tx;\n          if (seen[key]) continue;\n          seen[key] = 1;\n          q.push(key);\n        }\n      }\n      return false;\n    };\n    int l = 0;\n    int r = n * n;\n    while (l < r) {\n      int m = l + (r - l) \/ 2;\n      if (hasPath(m)) {\n        r = m;\n      } else {\n        l = m + 1;\n      }\n    }\n    return l;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>On an N x N&nbsp;grid, each square&nbsp;grid[i][j]&nbsp;represents the elevation at that point&nbsp;(i,j). Now rain starts to fall. At time&nbsp;t, the depth of the water everywhere&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71],"tags":[151,116,72],"class_list":["post-4750","post","type-post","status-publish","format-standard","hentry","category-heap","tag-head","tag-path","tag-priority-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4750","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=4750"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4750\/revisions"}],"predecessor-version":[{"id":4760,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4750\/revisions\/4760"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4750"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4750"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4750"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}