• 问题来源
• 问题简介

  提供一个只有0和1的二维矩阵，求出二维矩阵中每个点到0的最短曼哈顿距离。
  注：0到0的距离是0，

解题思路

Code

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        vector<vector<int>> dis(row, vector<int>(col, INT_MAX));
        int f_d[4][2] = {
            {0, 1}, {1, 0}, {0, -1}, {-1, 0}
        };
        queue<pair<int, int>> q;
        int x, y, nx, ny;
        // init queue, add all 0's (x, y) into q
        for (x = 0; x < col; x++) {
            for (y = 0; y < row; y++) {
                if (!matrix[y][x]) {
                    dis[y][x] = 0;
                    q.push(make_pair(x, y));
                }
            }
        }
        while (!q.empty()) {
            // broadcast the index, 1's value and add Index 1, 0's value and set Index 0
            auto& cur = q.front();
            x = cur.first;
            y = cur.second;
            for (int i = 0; i < 4; i++) {
                nx = x + f_d[i][0];
                ny = y + f_d[i][1];
                if (nx >= 0 && nx < col && ny >= 0 && ny < row) {
                    if (matrix[ny][nx] && dis[ny][nx] > dis[y][x] + 1) {
                        // the distance of matrix[ny][nx] should change
                        // and the relative index's distance may change too
                        // thus, put it into the queue
                        dis[ny][nx] = dis[y][x] + 1;
                        q.push(make_pair(nx, ny));
                    }
                }
            }

            q.pop();
        }
        return dis;
    }
};

运行结果