1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution
{
public:
    struct node
    {
        int x, y, step;
    };
    int go[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
    {
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> result(n, vector<int>(m, 99999));
        vector<vector<int>> vis(n + 1, vector<int>(m + 1, 0));
        queue<node> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0)
                {
                    q.push({i, j, 0});
                    vis[i][j] = 1;
                }
        while (!q.empty())
        {
            node now = q.front();
            q.pop();
            result[now.x][now.y] = min(result[now.x][now.y], now.step);
            for (int i = 0; i < 4; i++)
            {
                int xx = now.x + go[i][0];
                int yy = now.y + go[i][1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy])
                {
                    if (matrix[xx][yy] == 1)
                        q.push({xx, yy, now.step + 1});
                    else
                        q.push({xx, yy, now.step});
                    vis[xx][yy] = 1;
                }
            }
        }
        return result;
    }
};