<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>

vector<int> dr = {0 , -1 , 0 , 1};
vector<int> dc = {-1 , 0 , 1 , 0};

class Solution {
public:
    // int bfs(vector<vector<int>>& mat,int frow,int fcol){
    //     int m=mat.size(),n=mat[0].size();
    //     vector<vector<int>> vis(m , vector<int>(n , 0));
    //     vis[frow][fcol] = 1;
    //     priority_queue<vector<long long>,vector<vector<long long>>,greater<vector<long long>>> q;
    //     vector<long long> temp({0,frow,fcol});
    //     q.push(temp);

    //     while(!q.empty()){
    //         int curr=q.top()[0];
    //         int row=q.top()[1];
    //         int col=q.top()[2];
    //         q.pop();

    //         if(mat[row][col]==0){
    //             return curr;
    //             break;
    //         }
    //         for(int t = 0 ; t<4 ; t++){
    //             int nrow = row+dr[t];
    //             int ncol = col+dc[t];
    //             bool valid = (nrow>=0 and nrow<m and ncol>=0 and ncol<n);
    //             if(valid){
    //                 if(!vis[nrow][ncol]){
    //                     vis[nrow][ncol] = 1;
    //                     q.push({curr+1 , nrow , ncol});
    //                 }
    //             }
    //         }
    //     }
    //     return -1;
    // }

    vector<vector<int>> updateMatrix(vector<vector<int>>& mat){
        int m=mat.size(),n=mat[0].size();
        vector<vector<int>> ans(mat.size(),vector<int> (mat[0].size(),0));
        vector<vector<int>> vis(m , vector<int>(n , 0));
        priority_queue<vector<long long>,vector<vector<long long>>,greater<vector<long long>>> q0;
        int count=0;
        for(int i=0;i<mat.size();i++){
            for(int j=0;j<mat[i].size();j++){
                if(mat[i][j]==0){
                    q0.push({0,i,j});
                    vis[i][j]=1;
                }
                else count++;
                
            }
        }

        while(!q0.empty()){
            if(count==0)break;
            int curr=q0.top()[0];
            int row=q0.top()[1];
            int col=q0.top()[2];
            q0.pop();
            if(mat[row][col]==1){
                count--;
                ans[row][col]=curr;
                // continue;
            }
            for(int t = 0 ; t<4 ; t++){
                int nrow = row+dr[t];
                int ncol = col+dc[t];
                bool valid = (nrow>=0 and nrow<m and ncol>=0 and ncol<n);
                if(valid){
                    if(!vis[nrow][ncol]){
                        vis[nrow][ncol] = 1;
                        q0.push({curr+1 , nrow , ncol});
                    }
                }
            }
        }
        return ans;
    }
};

           // for(int i=-1;i<=1;i++){
            //     for(int j=-1;j<=1;j++){
            //         if(i==-1 && (j==-1 || j==1))continue;
            //         if(i==1 && (j==-1 || j==1))continue;
            //         if(i==0 && j==0)continue;
            //         int nrow=row+i,ncol=col+j;
            //         if(nrow<0 || nrow>=m || ncol<0 || ncol>=n)continue;



            //         if(mat[nrow][col]==0){
            //             ans[row][col]=1;
            //             return ans[frow][fcol]=curr+1;
            //             cout<<"hello";
            //         }
            //         else{
            //             temp={curr+1,nrow,ncol};
            //             q.push(temp);
            //         }
            //     }
            // }
56485