为什么简洁网站会受到用户欢迎,建设银行网站如何下载u盾,做家乡网站源代码,自己给网站做logo1. 题目
在给定的二维二进制数组 A 中#xff0c;存在两座岛。#xff08;岛是由四面相连的 1 形成的一个最大组。#xff09;
现在#xff0c;我们可以将 0 变为 1#xff0c;以使两座岛连接起来#xff0c;变成一座岛。
返回必须翻转的 0 的最小数目。#xff08;可…1. 题目
在给定的二维二进制数组 A 中存在两座岛。岛是由四面相连的 1 形成的一个最大组。
现在我们可以将 0 变为 1以使两座岛连接起来变成一座岛。
返回必须翻转的 0 的最小数目。可以保证答案至少是 1。
示例 1
输入[[0,1],[1,0]]
输出1示例 2
输入[[0,1,0],[0,0,0],[0,0,1]]
输出2示例 3
输入[[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]]
输出1提示
1 A.length A[0].length 100
A[i][j] 0 或 A[i][j] 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/shortest-bridge 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. BFS解题
先找到第一个1然后把相连的1用BFS全部加入到队列Q里然后对Q再使用BFS直到找到1就连通了两座岛
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};//移动方向
public:int shortestBridge(vectorvectorint A) {queuepairint,int q;//第二次BFS用的队列queuepairint,int firstLand;//第一次BFS用的队列int i, j, n A.size(), k, x, y, step0, size;bool found false;vectorvectorbool visited(n,vectorbool (n, false));for(i 0; i n; i){for(j 0; j n; j)if(A[i][j]){q.push(make_pair(i,j));firstLand.push(make_pair(i,j));visited[i][j] true;found true;break;}if(found)break;}pairint,int tp;while(!firstLand.empty())//第一次BFS{tp firstLand.front();firstLand.pop();for(k 0; k 4; k){x tp.first dir[k][0];y tp.second dir[k][1];if(x0 xn y0 yn A[x][y] !visited[x][y]){firstLand.push(make_pair(x,y));q.push(make_pair(x,y));//q里存储了所有的第一个岛的点visited[x][y] true;}}}found false;while(!q.empty())//第二次BFS{size q.size();while(size--)//向外扩展一层{tp q.front();q.pop();for(k 0; k 4; k){x tp.first dir[k][0];y tp.second dir[k][1];if(x0 xn y0 yn !visited[x][y]){if(A[x][y] 0){q.push(make_pair(x,y));visited[x][y] true;}else//找到1了连通了{found true;break;}}}if(found)break;}step;if(found)break;}return step-1;//最后一步1不算所以-1}
};
