542. 01 Matrix --------M

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

 

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

 

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

 

A:

BFS

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m==0)
            return vector<vector<int>>{};
        int n = matrix[0].size();
        vector<vector<int>> res(m, vector<int>(n,-1));
        vector<vector<int> > curLayer;
        for(int i =0;i<m;i++){
            for(int j =0;j<n;j++){
                if(matrix[i][j]==0){
                    res[i][j]=0;
                    curLayer.push_back(vector<int>{i,j});
                }
            }
        }
        int layerCount = 0;
        while(not curLayer.empty()){
            layerCount++;
            vector<vector<int> > nextLayer;
            for(auto pos : curLayer){
                int x = pos[0], y = pos[1];
                if(x-1>=0 && res[x-1][y] < 0 ){
                    res[x-1][y] = layerCount;
                    nextLayer.push_back(vector<int>{x-1,y});
                }
                if(x+1 < m && res[x+1][y] < 0 ){
                    res[x+1][y] = layerCount;
                    nextLayer.push_back(vector<int>{x+1,y});
                }
                if(y-1>=0 && res[x][y-1] < 0 ){
                    res[x][y-1] = layerCount;
                    nextLayer.push_back(vector<int>{x,y-1});
                }
                if(y+1 < n && res[x][y+1] < 0){
                    res[x][y+1] = layerCount;
                    nextLayer.push_back(vector<int>{x,y+1});
                }
            }
            curLayer = nextLayer;
        }
        return res;
    }
};