class Solution {public:    vector
     
      
       > res;    int m, n;    vector
       
        
         > updateMatrix(vector
         
          
           >& matrix) { m = matrix.size(); if (m == 0) return res; n = matrix[0].size(); if (n==0) return res; res = vector
           
            
             >(m, vector
             
              (n, INT_MAX)); queue
              
               
                > q; static int dirs[] = { -1, 0, 1, 0, -1 }; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == 0) { res[i][j] = 0; q.push({i,j}); } while (!q.empty()) { auto p = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int x = p.first + dirs[k]; int y = p.second + dirs[k+1]; if (x < 0 || y < 0 || x >= m || y >= n || res[p.first][p.second] + 1 >= res[x][y]) continue; res[x][y] = res[p.first][p.second] + 1; q.push({x, y}); } } return res; }};/* DFS: slowclass Solution {public: vector
                
                 
                  > res; int m, n; vector
                  
                   
                    > updateMatrix(vector
                    
                     
                      >& matrix) { m = matrix.size(); if (m == 0) return res; n = matrix[0].size(); if (n==0) return res; res = vector
                      
                       
                        >(m, vector
                        
                         (n, INT_MAX)); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == 0) { res[i][j] = 0; dfs(matrix, i, j); } return res; } void dfs(vector
                         
                          
                           >& mx, int i, int j) { static int dirs[] = { -1, 0, 1, 0, -1 }; for (int d = 0; d < 4; d++) { int x = i + dirs[d]; int y = j + dirs[d+1]; if (x < 0 || x >= m || y < 0 || y >= n || res[i][j] + 1 >= res[x][y]) continue; res[x][y] = res[i][j] + 1; dfs(mx, x, y); } }};*//* each point BFS: too slowclass Solution {public: vector
                           
                            
                             > res; int m, n; vector
                             
                              
                               > updateMatrix(vector
                               
                                
                                 >& matrix) { m = matrix.size(); if (m == 0) return res; n = matrix[0].size(); if (n==0) return res; res = vector
                                 
                                  
                                   >(m, vector
                                   
                                    (n, INT_MAX)); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) helper(matrix, i, j); return res; } void helper(vector
                                    
                                     
                                      >& mx, int i, int j) { static int dirs[] = { -1, 0, 1, 0, -1 }; if (mx[i][j] == 0) { res[i][j] = 0; return; } vector
                                      
                                       
                                        > v(m, vector
                                        
                                         (n, false)); queue
                                         
                                          
                                           > q; q.push({i,j}); v[i][j] = true; int lv = 0; while (!q.empty()) { int qs = q.size(); lv++; while (qs-- > 0) { auto p = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int x = p.first + dirs[k]; int y = p.second + dirs[k+1]; if (x < 0 || y < 0 || x >= m || y >= n || v[x][y]) continue; if (mx[x][y] == 0) { res[i][j] = lv; return; } else { q.push({x, y}); v[x][y] = true; } } } } }};*/