01 矩阵

题目描述

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:

0 0 0
0 1 0
0 0 0

输出:

0 0 0
0 1 0
0 0 0

示例 2:

输入:

0 0 0
0 1 0
1 1 1

输出:

0 0 0
0 1 0
1 2 1

注意:

给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

题解：

进行广播搜索，先将所有为0的位置加入队列，并且把非0的位置设置为最大值，然后以此从队列头部取出位置，然后检查其上下左右位置的值是否大于当前位置的值+1， 若大于， 则更新，同时加入队列，直到队列为空。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        vector<vector<int> > res;
        int m = matrix.size();
        int n = matrix[0].size();
        if(m==0)
            return res;

        queue<pair<int,int> > que;

        //把非0元素置成INT_MAX, 把0元素加入队列
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(matrix[i][j]==1)
                    matrix[i][j]=INT_MAX;
                else
                    que.push({i,j});

        //从0开始上下左右搜索, 如果搜索出大于当前值+1, 则进行更新，并把更新后的坐标加入队列
        while(!que.empty())
        {
            pair<int,int> t = que.front();
            int i = t.first;
            int j = t.second;
            que.pop();
            if(i-1>=0&&matrix[i-1][j]>matrix[i][j]+1)
            {
                matrix[i-1][j] = matrix[i][j]+1;
                que.push({i-1,j});
            }

            if(j-1>=0&&matrix[i][j-1]>matrix[i][j]+1)
            {
                matrix[i][j-1] = matrix[i][j]+1;
                que.push({i,j-1});
            }

            if(i+1<m && matrix[i+1][j]>matrix[i][j]+1)
            {
                matrix[i+1][j] = matrix[i][j]+1;
                que.push({i+1,j});
            }

            if(j+1<n && matrix[i][j+1]>matrix[i][j]+1)
            {
                matrix[i][j+1] = matrix[i][j]+1;
                que.push({i,j+1});
            }    
        }

        return matrix;
    }
};