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:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- 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; } };
No comments:
Post a Comment