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的点到每一个不为0的点的距离，更新结果矩阵。

C++1 [超时]

struct Pos
{
    int i;
    int j;
    Pos(int a,int b){i=a,j=b;}
};
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int n=matrix.size();
        int m=matrix[0].size();

        vector<Pos> tmp;

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(matrix[i][j]==0)
                {
                    Pos zero(i,j); 
                    tmp.push_back(zero);
                }
            }
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(!matrix[i][j])
                    continue;
                int minDis = n+m;
                for(int k=0;k<tmp.size();k++)
                {
                    int curDis = abs(tmp[k].i - i) + abs(tmp[k].j - j);
                    if(minDis>curDis)
                        minDis = curDis;
                }
                matrix[i][j] = minDis;
            }
        }
        return matrix;
    }
};

第一次循环矩阵中的每个点，初始的跳过次数为0；相比较的参考值为base=0。如果这个点小于等于base，跳过，记录跳过的次数加1；否则，找这个点周围的四个点（上下左右）如果等于base，跳过，否则将这个矩阵的点的值加1。
第二次循环矩阵中每个点，初始的跳过次数为0；相比较的参考值为base=1。如果这个点小于等于base，跳过，记录跳过的次数加1；否则，找这个点周围的四个点（上下左右）如果等于base，跳过，否则将这个矩阵的点的值加1。
第三次...
直到...确定程序最后终止的条件，当跳过的次数达到矩阵总个数的时候，也就是所有点都直接被跳过，所得的矩阵为最后的结果。

多想想就能理解了。。

C++2

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

        int base = 0;
        int count = 0;
        while(count != n*m)
        {
            count = 0;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    if(matrix[i][j]<=base)
                    {
                        count++;
                        continue;
                    }

                    bool ava = false;
                    //top
                    if(j-1>=0)
                    {
                        if(matrix[i][j-1]==base)
                            ava = true;
                    }

                    //bottom
                    if(j+1<m)
                    {
                        if(matrix[i][j+1]==base)
                            ava = true;
                    }

                    //top
                    if(i-1>=0)
                    {
                        if(matrix[i-1][j]==base)
                            ava = true;
                    }

                    //bottom
                    if(i+1<n)
                    {
                        if(matrix[i+1][j]==base)
                            ava = true;
                    }

                    if(!ava)
                        matrix[i][j]++;
                    else
                        count++;
                }
            }
            base++;
        }

        return matrix;
    }

};