New Problem Solution -"Map of Highest Peak"

haoel · haoel · commit ff7023558e98 · 2021-03-26T00:48:45.000+08:00
diff --git a/README.md b/README.md
@@ -34,6 +34,7 @@ LeetCode
 |1773|[Count Items Matching a Rule](https://leetcode.com/problems/count-items-matching-a-rule/) | [C++](./algorithms/cpp/countItemsMatchingARule/CountItemsMatchingARule.cpp)|Easy|
 |1769|[Minimum Number of Operations to Move All Balls to Each Box](https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/) | [C++](./algorithms/cpp/minimumNumberOfOperationsToMoveAllBallsToEachBox/MinimumNumberOfOperationsToMoveAllBallsToEachBox.cpp)|Medium|
 |1768|[Merge Strings Alternately](https://leetcode.com/problems/merge-strings-alternately/) | [C++](./algorithms/cpp/mergeStringsAlternately/MergeStringsAlternately.cpp)|Easy|
+|1765|[Map of Highest Peak](https://leetcode.com/problems/map-of-highest-peak/) | [C++](./algorithms/cpp/mapOfHighestPeak/MapOfHighestPeak.cpp)|Medium|
 |1763|[Longest Nice Substring](https://leetcode.com/problems/longest-nice-substring/) | [C++](./algorithms/cpp/longestNiceSubstring/LongestNiceSubstring.cpp)|Easy|
 |1761|[Minimum Degree of a Connected Trio in a Graph](https://leetcode.com/problems/minimum-degree-of-a-connected-trio-in-a-graph/) | [C++](./algorithms/cpp/minimumDegreeOfAConnectedTrioInAGraph/MinimumDegreeOfAConnectedTrioInAGraph.cpp)|Hard|
 |1760|[Minimum Limit of Balls in a Bag](https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/) | [C++](./algorithms/cpp/minimumLimitOfBallsInABag/MinimumLimitOfBallsInABag.cpp)|Medium|
diff --git a/algorithms/cpp/mapOfHighestPeak/MapOfHighestPeak.cpp b/algorithms/cpp/mapOfHighestPeak/MapOfHighestPeak.cpp
@@ -0,0 +1,98 @@
+// Source : https://leetcode.com/problems/map-of-highest-peak/
+// Author : Hao Chen
+// Date   : 2021-03-26
+
+/***************************************************************************************************** 
+ *
+ * You are given an integer matrix isWater of size m x n that represents a map of land and water cells.
+ * 
+ * 	If isWater[i][j] == 0, cell (i, j) is a land cell.
+ * 	If isWater[i][j] == 1, cell (i, j) is a water cell.
+ * 
+ * You must assign each cell a height in a way that follows these rules:
+ * 
+ * 	The height of each cell must be non-negative.
+ * 	If the cell is a water cell, its height must be 0.
+ * 	Any two adjacent cells must have an absolute height difference of at most 1. 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).
+ * 
+ * Find an assignment of heights such that the maximum height in the matrix is maximized.
+ * 
+ * Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there 
+ * are multiple solutions, return any of them.
+ * 
+ * Example 1:
+ * 
+ * Input: isWater = [[0,1],[0,0]]
+ * Output: [[1,0],[2,1]]
+ * Explanation: The image shows the assigned heights of each cell.
+ * The blue cell is the water cell, and the green cells are the land cells.
+ * 
+ * Example 2:
+ * 
+ * Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
+ * Output: [[1,1,0],[0,1,1],[1,2,2]]
+ * Explanation: A height of 2 is the maximum possible height of any assignment.
+ * Any height assignment that has a maximum height of 2 while still meeting the rules will also be 
+ * accepted.
+ * 
+ * Constraints:
+ * 
+ * 	m == isWater.length
+ * 	n == isWater[i].length
+ * 	1 <= m, n <= 1000
+ * 	isWater[i][j] is 0 or 1.
+ * 	There is at least one water cell.
+ ******************************************************************************************************/
+
+class Cell{
+public:
+    int x;
+    int y;
+    int height;
+};
+
+class Solution {
+private:
+    void setHeight(vector<vector<int>>& height, 
+                   queue<Cell>& q,
+                   int x, int y, int h, 
+                   int m, int n) 
+    {
+        if (x < 0 || y < 0 || x>=m || y>=n ) return;
+        if (height[x][y] == -1) {
+            height[x][y] = h;
+            q.push({x, y, h});
+        }
+    }
+public:
+    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
+        
+        int m = isWater.size();
+        int n = isWater[0].size();
+        
+        vector<vector<int>> height(m, vector(n, -1));
+        queue<Cell> q;
+        
+        for (int i=0; i<m; i++) {
+            for (int j=0; j<n; j++) {
+                if (isWater[i][j]) {
+                    height[i][j] = 0;
+                    q.push({i, j, 0});
+                }
+            }
+        }
+        
+        while(!q.empty()){
+            auto cell = q.front(); q.pop();
+            setHeight(height, q, cell.x-1, cell.y, cell.height+1,  m, n);
+            setHeight(height, q, cell.x+1, cell.y, cell.height+1,  m, n);
+            setHeight(height, q, cell.x, cell.y-1, cell.height+1,  m, n);
+            setHeight(height, q, cell.x, cell.y+1, cell.height+1,  m, n);
+        }
+        
+        return height;
+    }
+                        
+};
