1、思路

• 问题是求每个格子离最近的0的距离，因此可以将所有的0节点作为初始节点添加到队列中，对其进行BFS搜索；

• 遍历队列，以零值元素为中心向四周展开，找到未遍历过的1值元素就计算它的距离，并让它进队，以便接下来搜索与该格子相邻的其他元素。

2、代码

class Solution {
public:
    typedef pair<int, int> PII;

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

        queue<PII> q;
        for (int i = 0; i < n; ++ i)
        {
            for (int j = 0; j < m; ++ j)
            {
                if (mat[i][j] == 0)
                {
                    res[i][j] = 0;
                    q.push(make_pair(i, j));
                }
                else
                {
                    res[i][j] = 2e4 + 10;       //取范围外的一个大数
                }
            }
        }

        //方向偏移量
        vector<PII> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

        while (!q.empty())
        {
            PII pos = q.front();
            q.pop();

            for (PII dir : dirs)
            {
                int x = pos.first + dir.first;  //计算下一元素的坐标
                int y = pos.second + dir.second;

                if (x >= 0 && x < n && y >= 0 && y < m)
                {
                    //判断下一元素是否为还未遍历过的 1 值元素
                    //因为遍历过的 1 值元素与当前元素相邻，他们的距离 <= 1
                    if (res[x][y] > res[pos.first][pos.second] + 1)
                    {
                        res[x][y] = res[pos.first][pos.second] + 1;
                        q.push(make_pair(x, y));
                    }
                }
            }
        }

        return res;
    }
};