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

    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};
    int n,m;

    // vector<vector<int>>visit;
    
    // int dfs(vector<vector<int>>&arr,int x,int y)
    // {
    //     if(arr[x][y]==0)return 0;

    //     visit[x][y]=1;

    //     int ans=INT_MAX;

    //     for(int k=0;k<4;k++)
    //     {
    //         int i=x+dx[k];
    //         int j=y+dy[k];

    //         if(i<0||i>=n||j<0||j>=m||visit[i][j])continue;
            
    //         ans=min(dfs(arr,i,j),ans);
    //     }
    //     visit[x][y]=0;
    //     if(ans==INT_MAX)return ans;
    //     return ans+1;
    // }


    int bfs(vector<vector<int>>&arr,int x,int y)
    {
        vector<vector<int>>visit(n,vector<int>(m,0));

        queue<vector<int>>q;
        q.push({x,y});
        visit[x][y]=1;
        int ans=0;
        while(!q.empty())
        {
            ans++;
            int s=q.size();
            while(s-->0)
            {
                int px=q.front()[0];
                int py=q.front()[1];
                q.pop();

                if(arr[px][py]==0)return ans-1;

                for(int k=0;k<4;k++)
                {
                    int i=px+dx[k];
                    int j=y+dy[k];

                    if(i<0||i>=n||j<0||j>=m||visit[i][j])continue;
                    
                    visit[i][j]=1;
                    q.push({i,j});

                }                
            }
        }
        return -1;
    }    


    vector<vector<int>> updateMatrix(vector<vector<int>>&arr) 
    {
        n=arr.size();
        m=arr[0].size();

        // visit.resize(n,vector<int>(m,0));

        vector<vector<int>>ans(n,vector<int>(m,0));
        
        //By dfs 
        // for(int i=0;i<n;i++)
        // {
        //     for(int j=0;j<m;j++)
        //     {
        //         if(arr[i][j])
        //         {
        //             ans[i][j]=dfs(arr,i,j);
        //         }
        //     }
        // }

        // for(int i=0;i<n;i++)
        // {
        //     for(int j=0;j<m;j++)
        //     {
        //         if(arr[i][j]==1)
        //         {
        //             ans[i][j]=bfs(arr,i,j);
        //         }
        //     }
        // }


        //Never search from 1 to 0 this is like search a path from 1 to 0 
        //But here in question it wants the distance from 0 
        // so if we start from all 0 in bfs manner then we get all 1 in one search and at min. distance;
        

        // queue<vector<int>>q;
        vector<vector<bool>>visit(n,vector<bool>(m,false));

        // for(int i=0;i<n;i++)
        // {
        //     for(int j=0;j<m;j++)
        //     {
        //         if(arr[i][j]==0)
        //         {
        //             q.push({i,j});
        //             visit[i][j]=true;
        //         }
        //     }
        // }


        // int step=0;

        // while(!q.empty())
        // {

        //     int sz=q.size();
        //     while(sz-->0)
        //     {
        //         int x=q.front()[0];
        //         int y=q.front()[1];
        //         q.pop();

        //         if(arr[x][y]==1)
        //         {
        //             ans[x][y]=step;
        //         }

        //         for(int k=0;k<4;k++)
        //         {
        //             int i=x+dx[k];
        //             int j=y+dy[k];

        //             if(i<0||i>=n||j<0||j>=m||visit[i][j])continue;

        //             visit[i][j]=true;
        //             q.push({i,j});

        //         }

        //     }
        //     step++;
        // }



        //Another way of bfs

        // queue<vector<int>>q; // {x,y,steps_to_reach_at_zero}

        // for(int i=0;i<n;i++)
        // {
        //     for(int j=0;j<m;j++)
        //     {
        //         if(arr[i][j]==0)
        //         {
        //             q.push({i,j,0});
        //             visit[i][j]=true;
        //         }
        //     }
        // }  

        // while(!q.empty())
        // {
        //     int x=q.front()[0];
        //     int y=q.front()[1];
        //     int s=q.front()[2];
        //     q.pop();

        //     ans[x][y]=s;

        //     for(int k=0;k<4;k++)
        //     {
        //         int i=x+dx[k];
        //         int j=y+dy[k];

        //         if(i<0||i>=n||j<0||j>=m||visit[i][j])continue;

        //         visit[i][j]=true;
        //         q.push({i,j,s+1});
        //     }

        // }


        queue<vector<int>>q;

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(arr[i][j]==0)
                {
                    q.push({i,j});
                    visit[i][j]=1;
                }
            }
        }

        vector<vector<int>>dist(n,vector<int>(m,0));

        int level=0;
        while(!q.empty())
        {
            int sz=q.size();
            while(sz-->0)
            {
                int x=q.front()[0];
                int y=q.front()[1];
                q.pop();

                if(arr[x][y])
                {
                    dist[x][y]=level;
                }

                for(int k=0;k<4;k++)
                {
                    int i=x+dx[k];
                    int j=y+dy[k];

                    if(i<0||i>=n||j<0||j>=m||visit[i][j])continue;

                    visit[i][j]=1;

                    q.push({i,j});
                }
            }
            level++;
        }


        return dist;
        // return ans;
    }
};
54554