C++刷LeetCode（934. 最短的桥）【深度优先搜索】【广度优先搜索】
题目描述：在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）
示例 1：
输入：[,]
输出：1
示例 2：
输入：[,,]
输出：2
示例 3：
输入：[,,,,]
输出：1
提示：
1 <= A.length = A.length <= 100
A == 0 或 A == 1
class Solution {
private:
vector<vector<int> > direct = {{-1, 0},{0, -1}, {0, 1},{1, 0}};
public:
void dfs(vector<vector<int> >& A, int i, int j){
if(i < 0 || j < 0 || i >= A.size() || j >= A.size() || A == 0 || A == 2)return;
A = 2;
for(auto cha : direct){
dfs(A, i + cha, j + cha);
}
}
int bfs(vector<vector<int> >& A, vector<vector<int> >& index){
queue<vector<int>> store;
for(auto cha : index){
store.push({cha, cha});
}
int res = 0;
int len1 = A.size(), len2 = A.size();
bool flag = false;
while(!store.empty()){
vector<vector<int> > temp;
while(!store.empty()){
temp.push_back(store.front());
store.pop();
}
for(auto index : temp){
for(auto cha : direct){
int temp1 = index + cha, temp2 = index + cha;
if(temp1 < 0 || temp1 >= len1 || temp2 < 0 || temp2 >= len2)continue;
if(A == 2)return res;
if(A == 0){
flag = true;
store.push({temp1, temp2});
A = 3;
}
}
}
res++;
}
return INT_MAX;
}
int shortestBridge(vector<vector<int>>& A) {
//先标记一个岛，将其全部变为2；
int len1 = A.size(), len2 = A.size();
int temp1, temp2;
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
if(A == 1){
temp1 = i, temp2 = j;
break;
}
}
}
dfs(A, temp1, temp2);
vector<vector<int> >temp;
for(int i = 0 ; i < len1; i++){
for(int j = 0; j < len2; j++){
if(A == 1){
temp.push_back({i, j});
}
}
}
return bfs(A, temp);
}
}; 捣鼓了好几个小时{:10_284:}
页:
[1]