[leetcode]-542 01 Matrix

旧城等待， 2022-06-18 01:07 151阅读 0赞

![Center][]

基本思路：对每个cell，设与最近0的距离为d，按d=0~nRows+nCols进行对其附近的cell进行搜索，若搜索到0则立即返回当时的d值

d = 0 即对应自身为0的情形。

代码：

class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            int nRows = matrix.size();
            int nCols = matrix[0].size();
            vector<vector<int>> res(nRows);
            for(int i = 0; i < nRows; ++ i){
                res[i].resize(nCols);
            }
            for(int i = 0; i < nRows; ++ i){
                for(int j = 0; j < nCols; ++j){
                    if(matrix[i][j] == 0){
                        res[i][j] = 0;
                    }else{
                        for(int delta = 1; delta < nRows + nCols; ++ delta){
                            for(int m = 0; m <= delta; ++ m){
                                int x1 = i - m;
                                int x2 = i + m;
                                int y1 = j - (delta - m);
                                int y2 = j + (delta - m);
                                if((x1 >= 0 && y1 >= 0 && matrix[x1][y1] == 0) ||
                                   (x1 >= 0 && y2 < nCols && matrix[x1][y2] == 0) ||
                                   (x2 < nRows && y1 >= 0 && matrix[x2][y1] == 0) ||
                                   (x2 < nRows && y2 < nCols && matrix[x2][y2] == 0)){
                                    res[i][j] = delta;
                                    delta = nRows + nCols;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
            return res;
        }
    };

[Center]: /images/20220618/7b7683b227b740c8a4c20dfa753b5eed.png