糖逗 发表于 2020-4-17 00:40:36

C++刷leetcode（542. 01 矩阵）【广度优先搜索】

本帖最后由 糖逗 于 2020-5-8 17:59 编辑

题目描述：

给定一个由 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.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 == 0){
                  store.push(make_pair(i, j));
                  res=0;
                }
            }
      }

      int direct = {{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, cur_y = temp.second+direct;
                if(cur_x >= 0 && cur_x < row&&cur_y >=0&& cur_y < col){
                  if(res > res + 1){
                        res = res + 1;
                        store.push(make_pair(cur_x, cur_y));
                  }
                }
            }
            

      }
      return res;
    }


注意事项：
1.思路如图1
2.参考链接：https://leetcode-cn.com/problems/01-matrix/solution/c-bfsxiang-jie-by-yi-zhi-ri-shi-jiu/
3.参考链接：https://leetcode-cn.com/problems/01-matrix/solution/yan-du-si-lu-fen-xi-by-xi-xi-d/

fly3412 发表于 2020-4-17 01:08:51

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

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

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

感谢{:10_254:}

fly3412 发表于 2020-4-18 20:52:59

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

C/C++的人丁稀少啊~~~
找个回贴的都不容易。
页: [1]
查看完整版本: C++刷leetcode（542. 01 矩阵）【广度优先搜索】