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

糖逗

题目描述：

1. 
   
2. 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
   
3. 
   
4. 两个相邻元素间的距离为 1 。
   
5. 
   
6. 示例 1:
   
7. 输入:
   
8. 
   
9. 0 0 0
   
10. 0 1 0
    
11. 0 0 0
    
12. 输出:
    
13. 
    
14. 0 0 0
    
15. 0 1 0
    
16. 0 0 0
    
17. 示例 2:
    
18. 输入:
    
19. 
    
20. 0 0 0
    
21. 0 1 0
    
22. 1 1 1
    
23. 输出:
    
24. 
    
25. 0 0 0
    
26. 0 1 0
    
27. 1 2 1
    
28. 注意:
    
29. 
    
30. 给定矩阵的元素个数不超过 10000。
    
31. 给定矩阵中至少有一个元素是 0。
    
32. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

复制代码

1. vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
   
2.         int row = matrix.size(), col = matrix[0].size();
   
3.         vector<vector<int> > res (row, vector<int> (col, INT_MAX));
   
4.         pair<int, int> temp;
   
5.         queue<pair<int, int> > store;
   
6.         for(int i = 0; i < row; i++){
   
7.             for(int j = 0; j < col; j++){
   
8.                 if(matrix[i][j] == 0){
   
9.                     store.push(make_pair(i, j));
   
10.                     res[i][j]=0;
    
11.                 }
    
12.             }
    
13.         }
    
14. 
    
15.         int direct[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
    
16.         while(!store.empty()){
    
17.             temp = store.front();
    
18.             store.pop();
    
19.             for(int i = 0; i < 4; i++){
    
20.                 int cur_x = temp.first+direct[i][0], cur_y = temp.second+direct[i][1];
    
21.                 if(cur_x >= 0 && cur_x < row&&cur_y >=0&& cur_y < col){
    
22.                     if(res[cur_x][cur_y] > res[temp.first][temp.second] + 1){
    
23.                         res[cur_x][cur_y] = res[temp.first][temp.second] + 1;
    
24.                         store.push(make_pair(cur_x, cur_y));
    
25.                     }
    
26.                 }
    
27.             }
    
28.             
    
29. 
    
30.         }
    
31.         return res;
    
32.     }

复制代码

注意事项：
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++的人丁稀少啊~~~
找个回贴的都不容易。