99 lines
3.2 KiB
C++
99 lines
3.2 KiB
C++
// 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;
|
|
}
|
|
|
|
};
|