BFS over queue||C++33ms Beats 96.36%
IntuitionSolve it by using BFS over a queue.
The position (i, j) is using (i<<10)+j to pack
C++ & Python are made.Approach
let r=|isWater|, c=|isWater[0]|
let i
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Solve it by using BFS over a queue.
The position (i, j) is using `(i<<10)+j` to pack
C++ & Python are made.
# Approach
<!-- Describe your approach to solving the problem. -->
1. let `r=|isWater|, c=|isWater[0]|`
2. let `int d[5]={0, 1, 0, -1, 0}` 
3. Declare a 2D vector `H(r, vector<int>(c, -1))`
4. Declare `q` as a queue over ints
5. Transverse all `isWater[i][j]` ; if  `isWater[i][j]==1` set `H[i][j]=0` & push  `(i<<10)+j` to `q`
6. Use BFS to proceed as long as q is not empty as follows
```
for(int h=0; !q.empty(); h++){
    int qz=q.size();// qz=|q|
    for(int a=0; a<qz; a++){
        // obtain idx from front & unpack i, j
        int idx=q.front(), i=idx>>10, j=idx&((1<<10)-1);
        q.pop(); // pop
        for(int b=0; b<4; b++){// for the adjacent cell
            int s=i+d[b], t=j+d[b+1];
            if (s<0||s>=r||t<0||t>=c|| H[s][t]!=-1) 
                continue;// oustside of the matrix or visited
            q.push((s<<10)+t); // push to q
            H[s][t]=h+1; // set the value
        }
    }
}
```
7. return `H`
8. the container `q` can be implemented by using C-array which is slight faster
9.  Python code is made by using `deque` without packing data.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
 $$O(rc)$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
Extra: $O(1)$; if counting the returning answer  $$O(rc)$$
# Code||C++ 1st version 62ms Beats 91.02%|q array version 33ms Beats 96.36%
```cpp []
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        const int r=isWater.size(), c=isWater[0].size();
        const int d[5]={0, 1, 0, -1, 0};
        vector<vector<int>> H(r, vector<int>(c, -1));
        queue<int> q;
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if (isWater[i][j]){
                    int idx=(i<<10)+j;
                    H[i][j]=0;
                    q.push(idx);
                }
            }
        }
        for(int h=0; !q.empty(); h++){
            int qz=q.size();
            for(int a=0; a<qz; a++){
                int idx=q.front(), i=idx>>10, j=idx&((1<<10)-1);
                q.pop();
                for(int b=0; b<4; b++){
                    int s=i+d[b], t=j+d[b+1];
                    if (s<0||s>=r||t<0||t>=c|| H[s][t]!=-1) continue;
                    q.push((s<<10)+t);
                    H[s][t]=h+1;
                }
            }
        }
        return H;
    }
};
```
```C++ [C++ array for q]
int q[1000000];
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        const int r=isWater.size(), c=isWater[0].size();
        const int d[5]={0, 1, 0, -1, 0};
        vector<vector<int>> H(r, vector<int>(c, -1));
        int front=0, back=0;
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if (isWater[i][j]){
                    int idx=(i<<10)+j;
                    H[i][j]=0;
                    q[back++]=idx;
                }
            }
        }
        for(int h=0; front!=back; h++){
            int qz=back-front;
            for(int a=0; a<qz; a++){
                int idx=q[front], i=idx>>10, j=idx&((1<<10)-1);
                front++;
                for(int b=0; b<4; b++){
                    int s=i+d[b], t=j+d[b+1];
                    if (s<0||s>=r||t<0||t>=c|| H[s][t]!=-1) continue;
                    q[back++]=((s<<10)+t);
                    H[s][t]=h+1;
                }
            }
        }
        return H;
    }
};
```
# Python code

```
class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        r, c = len(isWater), len(isWater[0])
        d = (0, 1, 0, -1, 0)
        H = [[-1] * c for _ in range(r)]
        q = deque()
        for i, row in enumerate(isWater):
            for j, x in enumerate(row):
                if x == 1:
                    H[i][j] = 0
                    q.append((i, j))
        h = 0
        while q:
            qz = len(q)
            for a in range(qz):
                i, j = q.popleft()
                for b in range(4):
                    s, t = i + d[b], j + d[b + 1]
                    if s < 0 or s >= r or t < 0 or t >= c or H[s][t] != -1:
                        continue
                    q.append((s, t))
                    H[s][t] = h + 1
            h += 1
        return H

        
```
['Breadth-First Search', 'Matrix', 'C++', 'Python3']