{"id":8135,"date":"2021-02-20T21:19:36","date_gmt":"2021-02-21T05:19:36","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8135"},"modified":"2021-02-20T21:25:27","modified_gmt":"2021-02-21T05:25:27","slug":"leetcode-1765-map-of-highest-peak","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1765-map-of-highest-peak\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1765. Map of Highest Peak"},"content":{"rendered":"\n<p>You are given an integer matrix&nbsp;<code>isWater<\/code>&nbsp;of size&nbsp;<code>m x n<\/code>&nbsp;that represents a map of&nbsp;<strong>land<\/strong>&nbsp;and&nbsp;<strong>water<\/strong>&nbsp;cells.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If&nbsp;<code>isWater[i][j] == 0<\/code>, cell&nbsp;<code>(i, j)<\/code>&nbsp;is a&nbsp;<strong>land<\/strong>&nbsp;cell.<\/li><li>If&nbsp;<code>isWater[i][j] == 1<\/code>, cell&nbsp;<code>(i, j)<\/code>&nbsp;is a&nbsp;<strong>water<\/strong>&nbsp;cell.<\/li><\/ul>\n\n\n\n<p>You must assign each cell a height in a way that follows these rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The height of each cell must be non-negative.<\/li><li>If the cell is a&nbsp;<strong>water<\/strong>&nbsp;cell, its height must be&nbsp;<code>0<\/code>.<\/li><li>Any two adjacent cells must have an absolute height difference of&nbsp;<strong>at most<\/strong>&nbsp;<code>1<\/code>. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).<\/li><\/ul>\n\n\n\n<p>Find an assignment of heights such that the maximum height in the matrix is&nbsp;<strong>maximized<\/strong>.<\/p>\n\n\n\n<p>Return&nbsp;<em>an integer matrix&nbsp;<\/em><code>height<\/code><em>&nbsp;of size&nbsp;<\/em><code>m x n<\/code><em>&nbsp;where&nbsp;<\/em><code>height[i][j]<\/code><em>&nbsp;is cell&nbsp;<\/em><code>(i, j)<\/code><em>&#8216;s height. If there are multiple solutions, return&nbsp;<strong>any<\/strong>&nbsp;of them<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/01\/10\/screenshot-2021-01-11-at-82045-am.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> isWater = [[0,1],[0,0]]\n<strong>Output:<\/strong> [[1,0],[2,1]]\n<strong>Explanation:<\/strong> The image shows the assigned heights of each cell.\nThe blue cell is the water cell, and the green cells are the land cells.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/01\/10\/screenshot-2021-01-11-at-82050-am.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> isWater = [[0,0,1],[1,0,0],[0,0,0]]\n<strong>Output:<\/strong> [[1,1,0],[0,1,1],[1,2,2]]\n<strong>Explanation:<\/strong> A height of 2 is the maximum possible height of any assignment.\nAny height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == isWater.length<\/code><\/li><li><code>n == isWater[i].length<\/code><\/li><li><code>1 &lt;= m, n &lt;= 1000<\/code><\/li><li><code>isWater[i][j]<\/code>&nbsp;is&nbsp;<code>0<\/code>&nbsp;or&nbsp;<code>1<\/code>.<\/li><li>There is at least&nbsp;<strong>one<\/strong>&nbsp;water cell.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: BFS<\/strong><\/h2>\n\n\n\n<p>h[y][x] = min distance of (x, y) to any water cell.<\/p>\n\n\n\n<p>Time complexity: O(m*n)<br>Space complexity: O(m*n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {\n    const int m = isWater.size();\n    const int n = isWater[0].size();\n    vector<vector<int>> ans(m, vector<int>(n, INT_MIN));\n    queue<pair<int, int>> q;\n    for (int y = 0; y < m; ++y)\n      for (int x = 0; x < n; ++x)\n        if (isWater[y][x]) {\n          q.emplace(x, y);\n          ans[y][x] = 0;\n        }\n    const vector<int> dirs{0, -1, 0, 1, 0};    \n    while (!q.empty()) {\n      const auto [cx, cy] = q.front();\n      q.pop();\n      for (int i = 0; i < 4; ++i) {\n        const int x = cx + dirs[i];\n        const int y = cy + dirs[i + 1];\n        if (x < 0 || x >= n || y < 0 || y >= m) continue;\n        if (ans[y][x] != INT_MIN) continue;\n        ans[y][x] = ans[cy][cx] + 1;\n        q.emplace(x, y);\n      }      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer matrix&nbsp;isWater&nbsp;of size&nbsp;m x n&nbsp;that represents a map of&nbsp;land&nbsp;and&nbsp;water&nbsp;cells. If&nbsp;isWater[i][j] == 0, cell&nbsp;(i, j)&nbsp;is a&nbsp;land&nbsp;cell. If&nbsp;isWater[i][j] == 1, cell&nbsp;(i, j)&nbsp;is a&nbsp;water&nbsp;cell.&#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":[34,177,87],"class_list":["post-8135","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-medium","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8135","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=8135"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8135\/revisions"}],"predecessor-version":[{"id":8138,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8135\/revisions\/8138"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8135"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8135"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8135"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}