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]]
1 #思路1，使用BFS,but TLE : 2 1，the second <> is bool not int .vector<vector<bool>> vis(matrix.size(),vector<bool>(matrix[0].size(),false)); 3 2, we should store the location of adjacent element to queue,rather than the value. we get value by index. 4 q.push(val) is wrong,q.push(make_pair(i,j)) work. 5 class Solution { 6 public: 7 8 vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { 9 vector<vector<int>> res(matrix.size(),vector<int>(matrix[0].size(),0)); 10 vector<vector<bool>> vis(matrix.size(),vector<bool>(matrix[0].size(),false)); 11 for(int i=0;i<matrix.size();i++) 12 for(int j=0;j<matrix[0].size();j++) 13 { 14 if(matrix[i][j]==0) 15 res[i][j]=0; 16 else { 17 //q.clear(); 18 queue<pair<int,int>> q; 19 res[i][j] = find0(matrix,res,vis,q,i,j); 20 21 } 22 } 23 return res; 24 25 } 26 int find0(vector<vector<int>>& matrix,vector<vector<int>>& res,vector<vector<bool>> vis,queue<pair<int,int>> q,int i,int j) 27 { 28 q.push(make_pair(i,j)); 29 vis[i][j] = true; 30 int count = 0,len=0,val; 31 while(!q.empty()) 32 { 33 len = q.size(); 34 while(len--) 35 { 36 i = q.front().first,j = q.front().second; 37 val = matrix[i][j];q.pop(); 38 if(val==0) return count; 39 if(i-1>=0&&(!vis[i-1][j])) 40 { 41 q.push(make_pair(i-1,j)); 42 vis[i-1][j]=true; 43 } 44 if(j-1>=0&&(!vis[i][j-1])) 45 { 46 q.push(make_pair(i,j-1)); 47 vis[i][j-1]=true; 48 } 49 if(i+1<matrix.size()&&(!vis[i+1][j])) 50 { 51 q.push(make_pair(i+1,j)); 52 vis[i+1][j]=true; 53 } 54 if(j+1<matrix[0].size()&&(!vis[i][j+1])) 55 { 56 q.push(make_pair(i,j+1)); 57 vis[i][j+1]=true; 58 } 59 60 } 61 count++; 62 } 63 return -1; 64 } 65 };