<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:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> tr(mat.size(), vector<int>(mat[0].size(), -1));
        map<pair<int, int>, bool> pts;
        for (int i = 0; i < mat.size(); i++)
            for (int j = 0; j < mat[0].size(); j++)
                if (mat[i][j])
                    pts[{i, j}] = false;
                else
                    tr[i][j] = 0;
        int mv = 0, x, y;
        while (pts.size() > 0) {
            for (auto [k, v] : pts) {
                x = k.first;
                y = k.second;
                mv = INT_MAX;
                if (x > 0 && tr[x - 1][y] != -1 && mat[x - 1][y] == 0 && mv > tr[x - 1][y])
                    mv = tr[x - 1][y];
                if (y > 0 && tr[x][y - 1] != -1 && mat[x][y - 1] == 0 && mv > tr[x][y - 1])
                    mv = tr[x][y - 1];
                if (x < mat.size() - 1 && tr[x + 1][y] != -1 && mat[x + 1][y] == 0 && mv > tr[x + 1][y])
                    mv = tr[x + 1][y];
                if (y < mat[0].size() - 1 && tr[x][y + 1] != -1 && mat[x][y + 1] == 0 && mv > tr[x][y + 1])
                    mv = tr[x][y + 1];
                if (mv != INT_MAX) {
                    tr[x][y] = mv + 1;
                    pts[{x, y}] = true;
                }
            }
            for(auto it = pts.begin(); it != pts.end() ; )
                if (it->second) {
                    mat[it->first.first][it->first.second] = 0;
                    it = pts.erase(it);
                }
                else
                    it++;
        }
        return tr;
    }
};
41035