2018-09-18 542. 01 Matrix

题意：给你一个矩阵只包含元素0和1，求的一个矩阵，该矩阵在原矩阵为1的位置得出该元素距离最近的0的距离（仅能上下左右）。
解题思路：
动态规划思路，矩阵中的某一点，如果在原矩阵中是0，那么该点在当前矩阵中也是0,；如果在原矩阵中不为0，那么该点到0的最近距离可由该点附近的点（上下左右）的最小值+1得出。
使用两个循环，第一个循环从上至下、从左至右，第二次循环从下往上从右向左。
这样两次循序可保证一个点一定和周围的点比较过，且一定是最小值。

class Solution {
private:
    const int INTMAX = 0x4fffffff;
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> ans(n, vector<int>(m, INTMAX));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(matrix[i][j] == 0)
                    ans[i][j] = 0;
                else{
                    if(i > 0)
                        ans[i][j] = min(ans[i][j], ans[i-1][j]+1);
                    if(j > 0)
                        ans[i][j] = min(ans[i][j], ans[i][j-1]+1);
                }
        for(int i = n-1; i >= 0; i--)
            for(int j = m-1; j >=0; j--)
                if(ans[i][j] != 0){
                    if(i < n-1)
                        ans[i][j] = min(ans[i][j], ans[i+1][j]+1);
                    if(j < m-1)
                        ans[i][j] = min(ans[i][j], ans[i][j+1]+1);
                }
        return ans;
    }
};

注意：
一、二维vector的初始化
vector<vector<int>> ans(n, vector<int>(m, INTMAX));
n：该vector共有多少个行vector
vector<int>(m, INTMAX)：每个vector初始化，每个vector共有m个元素，每个元素的值为INTMAX。
二、从上之下从左至右、从下至上从右向左的动态规划思想。