« back

01 Matrix

Tags : array, matrix, dynamic-programming, leetcode, cpp, medium

Problem Statement - link #

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell

The distance between two adjacent cells is 1.

Examples #

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints #

Solutions #


class Solution {
    public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(mat[i][j]){
                    int a = n*m;
                    if(i>0) a=min(a,mat[i-1][j]);
                    if(j>0) a=min(a,mat[i][j-1]);
                    mat[i][j] = a+1;
                }        
        for(int i=n-1;i>=0;i--)
            for(int j=m-1;j>=0;j--)
                if(mat[i][j]){
                    int a = n*m;
                    if(i<n-1) a=min(a,mat[i+1][j]);
                    if(j<m-1) a=min(a,mat[i][j+1]);
                    mat[i][j] = min(mat[i][j],a+1);
                }
        return mat;
    }
};