題目描述
給定一個(gè)由 0 和 1 組成的矩陣，找出每個(gè)元素到最近的 0 的距離。
兩個(gè)相鄰元素間的距離為 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
注意:
給定矩陣的元素個(gè)數(shù)不超過 10000。
給定矩陣中至少有一個(gè)元素是 0。
矩陣中的元素只在四個(gè)方向上相鄰: 上、下、左、右。
分析
采用BFS算法
第一步，遍歷矩陣，所有的0值都可能是起點(diǎn)，保存到隊(duì)列，非0值設(shè)置成INT_MAX
第二步，遍歷隊(duì)列，取隊(duì)列頭的點(diǎn)，x, y。判斷上、下、左、右的點(diǎn)，如果大于matrix[x][y] + 1,則更新這些點(diǎn)的數(shù)值，并把更新后的點(diǎn)放進(jìn)隊(duì)列里面，因?yàn)檫@些點(diǎn)更新了，這些點(diǎn)周圍的點(diǎn)也可能需要更新
代碼
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;
}
};
