LetCode 매일 퀴즈 542.01 Matrix

제목 링크 542.01 Matrix 난이도: Medium
01 행렬의 모든 점과 주위 값이 0인 점의 가장 가까운 맨해튼 거리가 얼마인지 구하는 것이다.방법은 매우 많은데 예전에 성전 인터넷 경기의 문제가 이것과 마찬가지로 폭력적으로 모든 1을 대열에 넣고 그 다음에 bfs가 있었다는 것을 기억한다.나는 이번에 전후 두 번 dp에서 구한 것이다.코드는 다음과 같습니다.
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        const int Max=10000;
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int> >dp(m,vector<int>(n,Max));//m n Max
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(!matrix[i][j]) dp[i][j]=0;
                else{
                    dp[i][j]=min(i==0?Max:dp[i-1][j]+1,j==0?Max:dp[i][j-1]+1);
                }
            }
        }
        for(int i=m-1;i>=0;--i){
            for(int j=n-1;j>=0;--j){
                if(!matrix[i][j]) continue;
                dp[i][j]=min(dp[i][j],min(i==m-1?Max:dp[i+1][j]+1,j==n-1?Max:dp[i][j+1]+1));
            }
        }
        return dp;
    }
};
Runtime: 176 ms, faster than 98.13% of C++ online submissions for 01 Matrix. Memory Usage: 20.9 MB, less than 90.13% of C++ online submissions for 01 Matrix. Next challenges:

좋은 웹페이지 즐겨찾기