算法期中练习——1003. 最近的0

Description:

输入一个N*M的01矩阵A，对矩阵的每个位置，求至少经过多少步可以到达一个0. 每一步可以往上下左右走一格

Example:

例如：
A=
1 1 1
0 1 1
0 0 1

答案为
1 2 3
0 1 2
0 0 1

请为下面的Solution类实现解决这一问题的函数nearestZero，函数参数A为给出的01矩阵，A的行数和列数均不大于100. 函数的返回值是问题的答案.

class Solution {
public:
    vector<vector<int>> nearestZero(vector<vector<int>>& A) {
                        
    }
};

Solution #1：

暴力破解法：遍历二维数组，判断每一个位置上的数是否为0，若为0，即该位置到0的最近距离为0；反之，即该位置上的数不为0，此时再遍历二维数组，不断更新该位置上的数到0的最近距离，具体用到下面这条公式：
dist[i][j] = min(dist[i][j], abs(k - i) + abs(l - j));

代码如下

class Solution {
public:
    vector<vector<int>> nearestZero(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (rows == 0)
            return matrix;
        int cols = matrix[0].size();
        vector<vector<int> > dist(rows, vector<int>(cols, INT_MAX));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0)
                    dist[i][j] = 0;
                else {
                    for (int k = 0; k < rows; k++)
                        for (int l = 0; l < cols; l++)
                            if (matrix[k][l] == 0) {
                                // abs(k - i) + abs(l - j): distance from 0 to 1
                                dist[i][j] = min(dist[i][j], abs(k - i) + abs(l - j));
                            }
                }
            }
        }
        return dist;
    }
};

Solution #2：

遍历二维数组，将数值为0的位置(i, j)加入队列queue中，且置ans[i][j]=0，反之置为-1。
然后遍历队列，判断位置为0的上下左右是否不为0，即ans[row][col]==-1，若为-1，更新ans[i][j]=ans[u.first][u.second]+1，表示相邻的不为0的位置到0的最小距离可以为1，然后将(row, col)加入队列queue中，继续循环。

代码如下

class Solution {
public:
    vector<vector<int>> nearestZero(vector<vector<int>>& matrix) {
        vector<vector<int>> ans;
        queue<pair<int, int>> Q;
        const int D[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        int n, m, row, col, i, j;
        pair<int, int> u;
        n = matrix.size();
        m = matrix[0].size();
        ans.resize(n);
        for (i = 0; i < n; i++) ans[i].resize(m);

        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    Q.push(make_pair(i, j));
                    ans[i][j] = 0;
                }
                else {
                    ans[i][j] = -1;
                }
            }
        }
        while (!Q.empty()) {
            u = Q.front();
            Q.pop();
            for (i = 0; i < 4; i++) {
                row = u.first + D[i][0];
                col = u.second + D[i][1];
                if (row >= 0 && row < n && col >= 0 && col < m && ans[row][col] == -1) {
                    ans[row][col] = ans[u.first][u.second] + 1;
                    Q.push(make_pair(row, col));
                }
            }
        }
        return ans;
    }
};