1765: Map-of-Highest-Peak
Medium

table of contents

i love trivial BFS!!!!

Just create a queue of all the water cells. Then, for each water level, iterate through the queue of water cells (and simultaneously pop them out of the queue), whilst traversing to all its unseen neighbouring cells, labelling each one height+1 of the previous cell. For every unseen neighbouring cell that you visit, consequently push it to the end of the queue.

Then, just repeat this process until you fill out your ans grid maximising heights.

code

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> ans (m, vector<int>(n, -1));
        queue <pair<int, int>> cells;
        int counter = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isWater[i][j] == 1) {
                    ans[i][j] = 0;
                    cells.push({i, j});
                }
            }
        }
        int direction[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!cells.empty()) {
            int size = cells.size();
            for (int i = 0; i < size; ++i) {
                pair<int, int> coordinate = cells.front();
                cells.pop();
                for (int j = 0; j < 4; ++j) {
                    int row = coordinate.first + direction[j][0];
                    int col = coordinate.second + direction[j][1];
    
                    if (row > -1 and row < m and col > -1 and col < n and ans[row][col] == -1) {
                        cells.push({row, col});
                        ans[row][col] = counter+1;
                    }
                }
            }
            ++counter;
        }
        return ans;
    }
};

complexity