<p>Given an <code>m x n</code> binary matrix <code>mat</code>, return <em>the distance of the nearest </em><code>0</code><em> for each cell</em>.</p>

<p>The distance between two adjacent cells is <code>1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> mat = [[0,0,0],[0,1,0],[0,0,0]]
<strong>Output:</strong> [[0,0,0],[0,1,0],[0,0,0]]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> mat = [[0,0,0],[0,1,0],[1,1,1]]
<strong>Output:</strong> [[0,0,0],[0,1,0],[1,2,1]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>4</sup></code></li>
	<li><code>mat[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
	<li>There is at least one <code>0</code> in <code>mat</code>.</li>
</ul>

class Solution {
    private:
        deque<pair<int,int>> edgeCases;
        vector<vector<int>> solution;
        int count = 0;
        bool isValid(pair<int,int> pos){
            if(pos.first < 0 || pos.second < 0 || pos.first >= solution.size() || pos.second >= solution[0].size()) return false;
            if(solution[pos.first][pos.second] != -1) return false;
            return true;
        }

        void outline(pair<int,int> center){
            pair<int,int> left = {center.first,center.second-1};
            pair<int,int> right = {center.first,center.second+1};
            pair<int,int> up = {center.first-1,center.second};
            pair<int,int> down = {center.first+1,center.second};
            if(isValid(left)) {
                count--;
                solution[left.first][left.second] = solution[center.first][center.second]+1;
                edgeCases.push_back(left);
            }
            if(isValid(right)) {
                count--;
                solution[right.first][right.second] = solution[center.first][center.second]+1;
                edgeCases.push_back(right);
            }
            if(isValid(up)) {
                count--;
                solution[up.first][up.second] = solution[center.first][center.second]+1;
                edgeCases.push_back(up);
            }
            if(isValid(down)) {
                count--;
                solution[down.first][down.second] = solution[center.first][center.second]+1;
                edgeCases.push_back(down);
            }

        }
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
            for(int i = 0; i < mat.size(); i++){
                solution.push_back(vector<int>());
                for(int j = 0; j < mat[0].size(); j++){
                    if(mat[i][j] == 0) {
                        edgeCases.push_back({i,j});
                        solution[i].push_back(0);
                    } else {
                        count++;
                        solution[i].push_back(-1);
                    }
                }
            }
           // printSolution();
            while(count > 0){
                int size = edgeCases.size();
                for(int i = 0; i < size; i++){
                    outline(edgeCases.front());
                   // printSolution();
                    edgeCases.pop_front();
                }
            }
            return solution;
        }

        void printSolution(){
            for(vector<int> list: solution){
                for(int i: list){
                    cout << i << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
};

// #include <climits>
// class Solution {
// private:
//     vector<vector<int>> solution;
//     set<pair<int,int>> seen;

//     void addNeighbors(vector<vector<int>>& mat, vector<pair<int,int>> &inOrder,int row, int col){
//         if(col > 0 && seen.count({row,col-1}) == 0) inOrder.push_back({row,col-1}); // Left
//         if(col < mat[0].size()-1 && seen.count({row,col+1}) == 0) inOrder.push_back({row,col+1}); // Right
//         if(row > 0 && seen.count({row-1,col}) == 0) inOrder.push_back({row-1,col}); // Up
//         if(row < mat.size() - 1 && seen.count({row+1,col}) == 0) inOrder.push_back({row+1,col}); // Down
//     }

//     // int getMin(int row, int col){
        
//     // }

//     int findVal(vector<vector<int>>& mat, int row, int col){
//         vector<pair<int,int>> inOrder;
//         seen.insert({row,col});
//         addNeighbors(mat,inOrder,row,col);
//         for(int i = 0; i < inOrder.size(); i++) {
//             if(solution[inOrder[i].first][inOrder[i].second] == 0) {
//                 solution[row][col] = 1;
//                 return 1;
//             }
//         }
        
//         int min = mat.size() + mat[0].size()-2;
//         for(pair<int,int> p: inOrder){
//             if(solution[p.first][p.second] == -1) {
//                 min = std::min(findVal(mat,p.first,p.second),min);
//             } else {
//                 min = std::min(min,solution[p.first][p.second]);
//             }
//         }
//         return min+1;
//     }

// public:
//     vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
//         for(int i = 0; i < mat.size(); i++){
//             solution.push_back(vector<int>());
//             for(int j = 0; j < mat[0].size(); j++){
//                 if(mat[i][j] == 0) {
//                     solution[i].push_back(0);
//                 } else {
//                     solution[i].push_back(-1);
//                 }
//             }
//         }

//         for(int i = 0; i < mat.size(); i++){
//             for(int j = 0; j < mat[0].size(); j++){
//                 if(solution[i][j] == -1) {
//                     seen.clear();
//                     solution[i][j] = findVal(mat,i,j);
//                 }
//             }
//         }
//         return solution;
//     }
// };
41035