leetcode 542. 01 Matrix 距离0最近的距离 + 正反遍历 + 动态规划DP

喜欢ヅ旅行 2022-06-03 03:41 171阅读 0赞

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  
Note:  
The number of elements of the given matrix will not exceed 10,000.  
There are at least one 0 in the given matrix.  
The cells are adjacent in only four directions: up, down, left and right.

本提提题意很简单，就是很明显的DP动态规划，注意要像4各方刚去计算

**需要注意和学习的地方就是正向遍历一次，然后需要反向遍历一次**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
        {
            int m = mat.size(), n = mat[0].size();
            vector<vector<int>> res(m, vector<int>(n, max(m, n)));
            for (int i = 0; i < m; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    if (mat[i][j] == 0)
                        res[i][j] = 0;
                    else
                    {
                        if (i > 0)
                            res[i][j] = min(res[i][j], res[i - 1][j] + 1);
                        if (j > 0)
                            res[i][j] = min(res[i][j], res[i][j - 1] + 1);
                    }
                }
            }
            for (int i = m - 1; i >= 0; --i)
            {
                for (int j = n - 1; j >= 0; --j)
                {
                    if (res[i][j] != 0)
                    {
                        if (i + 1 < m)
                            res[i][j] = min(res[i][j], res[i + 1][j] + 1);
                        if (j + 1 < n)
                            res[i][j] = min(res[i][j], res[i][j + 1] + 1);
                    }
                }
            }
            return res;
        }
    };