C++刷LeetCode（934. 最短的桥）【深度优先搜索】【广度优先搜索】

糖逗

题目描述：

1. 在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
   
2. 
   
3. 现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
   
4. 
   
5. 返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）
   
6. 
   
7. 
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入：[[0,1],[1,0]]
    
12. 输出：1
    
13. 示例 2：
    
14. 
    
15. 输入：[[0,1,0],[0,0,0],[0,0,1]]
    
16. 输出：2
    
17. 示例 3：
    
18. 
    
19. 输入：[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
    
20. 输出：1
    
21. 
    
22. 
    
23. 提示：
    
24. 
    
25. 1 <= A.length = A[0].length <= 100
    
26. A[i][j] == 0 或 A[i][j] == 1
    

复制代码

1. class Solution {
   
2. private:
   
3.     vector<vector<int> > direct = {{-1, 0},  {0, -1}, {0, 1},  {1, 0}};
   
4. public:
   
5.     void dfs(vector<vector<int> >& A, int i, int j){
   
6.         if(i < 0 || j < 0 || i >= A.size() || j >= A[0].size() || A[i][j] == 0 || A[i][j] == 2)return;
   
7.         A[i][j] = 2;
   
8.         for(auto cha : direct){
   
9.             dfs(A, i + cha[0], j + cha[1]);
   
10.         }
    
11.     }
    
12.     int bfs(vector<vector<int> >& A, vector<vector<int> >& index){
    
13.         queue<vector<int>> store;
    
14.         for(auto cha : index){
    
15.             store.push({cha[0], cha[1]});
    
16.         }
    
17.         int res = 0;
    
18.         int len1 = A.size(), len2 = A[0].size();
    
19.         bool flag = false;
    
20.         while(!store.empty()){
    
21.             vector<vector<int> > temp;
    
22.             while(!store.empty()){
    
23.                 temp.push_back(store.front());
    
24.                 store.pop();
    
25.             }
    
26.             for(auto index : temp){
    
27.                 for(auto cha : direct){
    
28.                     int temp1 = index[0] + cha[0], temp2 = index[1] + cha[1];
    
29.                     if(temp1 < 0 || temp1 >= len1 || temp2 < 0 || temp2 >= len2)continue;
    
30.                     if(A[temp1][temp2] == 2)return res;
    
31.                     if(A[temp1][temp2] == 0){
    
32.                         flag = true;
    
33.                         store.push({temp1, temp2});
    
34.                         A[temp1][temp2] = 3;
    
35.                     }
    
36.                 }
    
37.             }
    
38.             res++;
    
39.         }
    
40.         return INT_MAX;
    
41.     }
    
42.     int shortestBridge(vector<vector<int>>& A) {
    
43.         //先标记一个岛，将其全部变为2；
    
44.         int len1 = A.size(), len2 = A[0].size();
    
45.         int temp1, temp2;
    
46.         for(int i = 0; i < len1; i++){
    
47.             for(int j = 0; j < len2; j++){
    
48.                 if(A[i][j] == 1){
    
49.                    temp1 = i, temp2 = j;
    
50.                    break;
    
51.                 }
    
52.             }
    
53.         }
    
54.         dfs(A, temp1, temp2);
    
55.         vector<vector<int> >temp;
    
56.         for(int i = 0 ; i < len1; i++){
    
57.             for(int j = 0; j < len2; j++){
    
58.                 if(A[i][j] == 1){
    
59.                     temp.push_back({i, j});
    
60.                 }
    
61.             }
    
62.         }
    
63.         return bfs(A, temp);
    
64. 
    
65.     }
    
66. };

复制代码

糖逗

捣鼓了好几个小时