highestPeak.txt

1765. Map of Highest peak 
/*
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.
*\

class Solution {
    //this array is created to generate neighbour indexes
    int dx[4] = {-1,0,1,0};
    int dy[4] = {0,-1,0,1};

    //check if the indes is valid or not, also check if it not a water cell and not visited height will zero at that index
    bool isSafe(vector<vector<int>>& isWater, int r, int c, vector<vector<int>>& heights){
        if(r < 0 || c < 0 || r == isWater.size() || c == isWater[0].size() || isWater[r][c] == 1 || heights[r][c] > 0){
            return false;
        }
        return true;
    }

    void bfs(vector<vector<int>>& isWater, vector<vector<int>>& heights, queue<pair<int,int>>& q){
        while(q.size() != 0){
            int size = q.size();
            while(size--){
                int i = q.front().first;
                int j = q.front().second;
                q.pop();

                int height = heights[i][j];

                //generating neighbour indexes
                for(int b = 0; b < 4; b++){
                    int nI = i + dx[b];
                    int nJ = j + dy[b];

                    if(isSafe(isWater,nI,nJ,heights)){
                        heights[nI][nJ] = height + 1;
                        q.push({nI,nJ});
                    }
                }
            }
        }
    }
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size();
        int n = isWater[0].size();

        vector<vector<int>> heights(m,vector<int>(n,0));
        queue<pair<int,int>> q;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(isWater[i][j] == 1){
                    q.push({i,j});
                }
            }
        }
        bfs(isWater,heights,q);

        return heights;
    }
};