<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 {
public:
    using state=pair<int,int>;
    vector<vector<int>>vis;
    vector<vector<int>>dis;
    int N,M;
    bool isvalid(int x,int y){
        if(0<=x && x<N && 0<=y && y<M && vis[x][y]==0)
            return 1;
        return 0;
    }
    vector<state> neigh(state next){
        vector<state>neighbour;
        int dx[]={1,-1,0,0};
        int dy[]={0,0,1,-1};
        for(int i=0;i<4;i++){
            int x=next.first+dx[i];
            int y=next.second+dy[i];
            if(isvalid(x,y)){
                neighbour.push_back({x,y});
            }
        }
        return neighbour;
    }
    void bfs(vector<state>zeros){
        queue<state>q;
        for(int i=0;i<zeros.size();i++){
            state curr=zeros[i];
            q.push(curr);
        }
        while(!q.empty()){
            state next=q.front();
            q.pop();
            for(auto v:neigh(next)){
                if(!vis[v.first][v.second]){
                    vis[v.first][v.second]=1;
                    dis[v.first][v.second]=1+dis[next.first][next.second];
                    q.push(v);
                }
            }
        }
    }
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        N=mat.size();
        M=mat[0].size();
        vis.assign(N,vector<int>(M,0));
        dis.assign(N,vector<int>(M,1e9));
        vector<state>zeros;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(mat[i][j]==0){
                    zeros.push_back({i,j});
                    vis[i][j]=1;
                    dis[i][j]=0;
                }
            }
        }
        bfs(zeros);
        return dis;
    }
};
49146