542. 01 矩阵

*给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
注意：

1. 给定矩阵的元素个数不超过 10000。
2. 给定矩阵中至少有一个元素是 0。
3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。*

一开始想的是BFS，遍历数组，如果当前元素是1，则从当前位置开始BFS，这样的话，遍历数组用时$O(n^2)$，BFS用时$O(n^2)$，总体时间复杂度为$O(n^4)$，感觉不太行。

突然起了个想法，也可能是前两天写的两篇博客都是关于动态规划的，就想着这个能不能用动态规划做呢？然后就想出了下面的东西（其实我不确定这是不是对的）。
用$dp[i][j]$表示位于$(i,j)$的1到最近的 0 的距离。看一下下面的图：

要求$dp[i][j]$不就需要求它周围的这8个点的$dp$值，再加上1或者2不就好了吗。公式如下：
$dp[i][j]=min left { begin{array}{lr} dp[i-1][j-1]+2,\ dp[i-1][j]+1,\ dp[i-1][j+1]+2,\ dp[i][j-1]+1,\ dp[i][j+1]+1,\ dp[i+1][j-1]+2,\ dp[i+1][j]+1,\ dp[i+1][j+1]+2 end{array} right .$

一开始想到BFS是以$matrix[i][j]=1$

题目中告诉我们给定矩阵的元素个数不超过 10000，如果设置一个数组int visited[10000][10000]，这样内存不够用的，技巧是设置一个int visited[10000]，然后将位置$(i,j)$离散化处理，变成$i*n+j$

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        
        int next[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        
        vector<vector<int>> ans = matrix;
        
        int visited[10002] = {0};
        deque<pair<int, int>> d;
        
        int m = matrix.size(), n = matrix[0].size();;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    d.push_back(make_pair(i, j));
                    visited[i*n+j] = 1;
                }
            }
        }
        
        int step = 0;
        while (!d.empty()) {
            int len = d.size();
            for (int k = 0; k < len; k++) {
                pair<int, int> p = d.front();
                d.pop_front();
                int i = p.first, j = p.second;
                if (matrix[i][j] == 1) {
                    ans[i][j] = step;
                }
                for (int t = 0; t < 4; t++) {
                    int next_i = i+ next[t][0], next_j = j + next[t][1];
                    if (!(next_i < 0 || next_i >= matrix.size() || next_j < 0 || next_j >= matrix[0].size() || visited[next_i*n+next_j] == 1)) {
                        d.push_back(make_pair(next_i, next_j));
                        visited[next_i*n+next_j] = 1;
                    }
                }
            }
            step++;
        }
        return ans;
    }
};