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。
二、从上之下从左至右、从下至上从右向左的动态规划思想。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,421评论 0 2
  • 第一次感知到时间的流逝是一次晚上在操场跑步,我听着歌,忽然之间,感觉时间像流沙一样,在身体里或者在身体之外某个地方...
    HandsomeKing阅读 399评论 0 0
  • 你说,你喜欢长发飘飘 就像漫画里走出的姑娘 你说,你喜欢温柔乖巧 就像童话里的田螺姑娘 你说,你喜欢我文采飞扬 喜...
    柏浅歌阅读 223评论 5 1
  • 人都是有惰性的,尤其是上班累成狗,回家就想瘫软的时候,惰性上身,很容易就陷入了“找借口-懊悔”的死循环中。 如何克...
    小叶弯弯阅读 406评论 0 0
  • Block Pointer是这样定义的: 回传值(^名字)(参数列); 例:typedefvoid(^change...
    木木_mislay阅读 208评论 0 1