01 Matrix
题目大意，求解矩阵中每个位置和离它最近的0之间的距离。
2.分析我刚开始想到的是DFS，但我没有去实现，参考Grandyang的思路。其实，求距离用BFS是比较合理的，像经典的迷宫问题，都是从一端探索到另外一端。而这里，是有多个入口的。题目求解矩阵中'1'所处的位置跟离它最近的0之间的距离，所以我们以每个0所处的位置作为需要探索的起点，放在队列当中；若矩阵中的元素值为1，则初始化为INT_MAX。若当前探索的坐标越界或者此时当前的距离小于或等于当前探索的点的值+1，则说明当前的值是最优值，无需更新。
class Solution {
public:
vector<vector> updateMatrix(vector<vector>& matrix) {
int m = matrix.size(), n = matrix[0].size();
queue<pair> points;
for (int i = 0; i < m; ++i){
for (int j = 0; j < n; ++j){
if (matrix[i][j] == 0) points.push({i, j});
else matrix[i][j] = INT_MAX;
}
}
vector<vector> moves{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; //左上右下
while (!points.empty()){
pair point = points.front();
points.pop();
for (auto move : moves){
int x = point.first + move[0];
int y = point.second + move[1];
if (x = m || y = n ||
matrix[x][y] <= matrix[point.first][point.second] + 1)
continue; //越界或者大于当前的最小值
matrix[x][y] = matrix[point.first][point.second] + 1; //更新当前值
points.push({x, y});
}
}
return matrix;
}
};
[1]https://www.cnblogs.com/grandyang/p/6602288.html
作者：Czy_whlg
