[C++] a other BFS find Solution base on Manhattan Distance


  • 0
    L
    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            vector<vector<int>> m;
            for (int i=0; i < matrix.size(); ++i) {
                vector<int> row;
                for (int j=0; j < matrix[0].size(); ++j) {
                    if (matrix[i][j] == 0) {
                        row.push_back(0);
                        continue;
                    } 
                    
                    //up, down, left,right
                    for (int d=1;;++d) {
                        if (hasOne(i,j,d,matrix)) {
                            row.push_back(d);
                            break;
                        }
                    }
                }
                m.push_back(row);
            }
           return m; 
        }
        
        bool hasOne(int x, int y, int d ,vector<vector<int>>& m) {
            for (int i=0; i <= d; ++i) {
                  int j = d -i;
                  if (x-i >= 0 && y-j >= 0 && m[x-i][y-j] == 0) return true;
                  if (x+i < m.size() &&  y-j >= 0 && m[x+i][y-j] == 0) return true;
                  if (x-i >= 0 && y+j < m[0].size() && m[x-i][y+j] == 0) return true;
                  if (x+i < m.size() && y+j <m[0].size() && m[x+i][y+j] == 0) return true;
            }
         
    
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.