542. 01 矩阵

题目描述

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:
输入:

0 0 0
0 1 0
0 0 0

输出:

0 0 0
0 1 0
0 0 0

示例 2:
输入:

0 0 0
0 1 0
1 1 1

输出:

0 0 0
0 1 0
1 2 1

注意:

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

分析

采用BFS算法
第一步，遍历矩阵，所有的0值都可能是起点，保存到队列，非0值设置成INT_MAX
第二步，遍历队列，取队列头的点，x, y。判断上、下、左、右的点，如果大于matrix[x][y] + 1,则更新这些点的数值，并把更新后的点放进队列里面，因为这些点更新了，这些点周围的点也可能需要更新

代码

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        queue<pair<int,int>> q;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(matrix[i][j] == 0) {
                    q.push(make_pair(i, j));
                } else {
                    matrix[i][j] = INT_MAX;
                }
            }
        }
        
        while(!q.empty()){
            auto p = q.front();
            int x = p.first;
            int y = p.second;
            q.pop();
            int cur = matrix[x][y] + 1;
            if(x > 0 && matrix[x - 1][y] > cur) {
                matrix[x-1][y] = cur;
                q.push(make_pair(x - 1, y));
            }
            if(x < row - 1 && matrix[x + 1][y] > cur) {
                matrix[x + 1][y] = cur;
                q.push(make_pair(x + 1, y));
            }
            if(y > 0 && matrix[x][y - 1] > cur) {
                matrix[x][y - 1] = cur;
                q.push(make_pair(x, y - 1));
            }
            if(y < col - 1 && matrix[x][y + 1] > cur) {
                matrix[x][y + 1] = cur;
                q.push(make_pair(x, y + 1));
            }
        }
        return matrix;
    }
};

题目链接

https://leetcode-cn.com/problems/01-matrix/description/