问题:
给定n*m二维数组代表陆地和海洋。
1:海洋
0:陆地
对这个地图,进行高度赋值。
规定海洋高度一律为0。
相邻两个cell的高度差不能超过 1。(可以为 0 or 1)
那么要使map上获得最高高度。
求所得到地图高度。
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.
example 1:
example 2:
解法:BFS
- 状态:
- 当前cell的坐标 (i, j)
- visited,直接使用给定的数组来标记,高度!=-1的,则未标记过的。
- 这里,需要初始化,海洋节点高度为0,其他节点都为-1(未被标记过)。
- 选择:上下左右四个方向。且未被标记高度过。
- 那么每层层次==高度。
代码参考:
1 class Solution { 2 public: 3 int n,m; 4 int dir[5] = {1,0,-1,0,1}; 5 vector<vector<int>> highestPeak(vector<vector<int>>& isWater) { 6 n = isWater.size(); 7 m = isWater[0].size(); 8 queue<pair<int,int>> q; 9 for(int i=0; i<n; i++) { 10 for(int j=0; j<m; j++) { 11 isWater[i][j]=isWater[i][j]==1?0:-1; 12 if(isWater[i][j]==0) { 13 q.push({i,j}); 14 } 15 } 16 } 17 int level = 1; 18 while(!q.empty()) { 19 int sz = q.size(); 20 for(int c=0; c<sz; c++) { 21 auto [i,j] = q.front(); 22 q.pop(); 23 for(int k=1; k<5; k++) { 24 int x = i+dir[k-1]; 25 int y = j+dir[k]; 26 if(x<0 || y<0 || x>=n || y>=m || isWater[x][y]!=-1) continue; 27 q.push({x,y}); 28 isWater[x][y]=level; 29 } 30 } 31 level++; 32 } 33 return isWater; 34 } 35 };