[C++] BFS Detailed Explanation + Similar Problems
almost identical problem:\n994. Rotting Oranges\n\nMain idea:\n1. Push coordinates {i, j} to queue where isWater[i][j] = 1, basically having a queue of water co
almost identical problem:\n[994. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)\n\nMain idea:\n1. Push coordinates `{i, j}` to `queue` where `isWater[i][j] = 1`, basically having a queue of water coordinates. Do this for every (i,j)\n2. `BFS` every water coordinate\'s adjacent neighbor, while incrementing `height` for every `queue size` (just like level order traversal for trees)\n3. Only update height in matrix and push to queue if height can be smaller \n```\n    if(height < isWater[r][c]) {\n        isWater[r][c] = height;\n        q.push({r,c});\n    }\n  ```\n\nCode:\n```\n    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {\n        int m = isWater.size(), n = isWater[0].size(), dir[5] = {0, 1, 0, -1, 0}, INF = 1e6+1;\n        queue<pair<int,int>> q;\n        for(int i=0; i<m; i++) {\n            for(int j=0; j<n; j++) {\n                if(isWater[i][j]) {\n                    isWater[i][j]=0;\n                    q.push({i, j});\n                } else {\n                    isWater[i][j]=INF;\n                }\n            }\n        }\n        int height = 1;\n        while(!q.empty()) {\n            int size = q.size();\n            while(size--) {\n                auto cur = q.front(); q.pop();\n                for(int i=0; i<4; i++) {\n                    int r = cur.first + dir[i], c = cur.second + dir[i+1];\n                    if(r < 0 || c < 0 || r >= m || c >= n) {\n                        continue;\n                    }\n                    if(height < isWater[r][c]) {\n                        isWater[r][c] = height;\n                        q.push({r,c});\n                    }\n                }\n            }\n            height++;\n        }\n        return isWater;\n    }\n```\n\nTime Complexity:\n`O(M * N * (M + N))`
[]