C++刷leetcode（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。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        vector<vector<int> > res (row, vector<int> (col, INT_MAX));
        pair<int, int> temp;
        queue<pair<int, int> > store;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(matrix[i][j] == 0){
                    store.push(make_pair(i, j));
                    res[i][j]=0;
                } 
            }
        }

        int direct[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
        while(!store.empty()){
            temp = store.front();
            store.pop();
            for(int i = 0; i < 4; i++){
                int cur_x = temp.first+direct[i][0], cur_y = temp.second+direct[i][1];
                if(cur_x >= 0 && cur_x < row&&cur_y >=0&& cur_y < col){
                    if(res[cur_x][cur_y] > res[temp.first][temp.second] + 1){
                        res[cur_x][cur_y] = res[temp.first][temp.second] + 1;
                        store.push(make_pair(cur_x, cur_y));
                    }
                }
            }
            

        }
        return res;
    }

注意事项：
1.思路如图1
2.参考链接：https://leetcode-cn.com/problems ... -yi-zhi-ri-shi-jiu/
3.参考链接：https://leetcode-cn.com/problems ... -fen-xi-by-xi-xi-d/

fly3412

路过，学习一下。
帖子真完整！

糖逗

fly3412 发表于 2020-4-17 01:08
路过，学习一下。
帖子真完整！

感谢

fly3412

糖逗 发表于 2020-4-17 12:38
感谢

C/C++的人丁稀少啊~~~
找个回贴的都不容易。