生活随笔
收集整理的這篇文章主要介紹了
LeetCode 934 最短的桥
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目描述
在給定的二維二進制數組 A 中，存在兩座島。（島是由四面相連的
1 形成的一個最大
組。）現在，我們可以將
0 變為
1，以使兩座島連接起來，變成一座島。返回必須翻轉的
0 的最小數目。（可以保證答案至少是
1。）
題解
等同于求兩個島嶼之間的最近距離，使用廣度優先搜索。
代碼
class Solution
{
public
:void dfs(vector
<vector
<int>>& A
,int x
,int y
,int m
,int n
){if (x
<0||x
>=m
||y
<0||y
>=n
) return;que
.push({x
,y
});for (int k
=0;k
<4;k
++){int xx
=x
+d
[k
][0];int yy
=y
+d
[k
][1];if (xx
<0||xx
>=m
||yy
<0||yy
>=n
||A
[xx
][yy
]!=1) continue;A
[xx
][yy
]=2; dfs(A
,xx
,yy
,m
,n
);}}int bfs(vector
<vector
<int>>& A
,int m
,int n
){int res
=0;while (!que
.empty()){int cnt
=que
.size();for (int i
=0;i
<cnt
;i
++){int x
=que
.front().first
;int y
=que
.front().second
;que
.pop();for (int k
=0;k
<4;k
++){int xx
=x
+d
[k
][0];int yy
=y
+d
[k
][1];if (xx
<0||xx
>=m
||yy
<0||yy
>=n
||A
[xx
][yy
]==2) continue;if (A
[xx
][yy
]==1) return res
;A
[xx
][yy
]=2; que
.push({xx
,yy
});}}res
++;}return res
;}int shortestBridge(vector
<vector
<int>>& A
) { int m
=A
.size();if (!m
) return 0;int n
=A
[0].size();if (!n
) return 0;bool flag
=false
;for (int i
=0;i
<m
;i
++){for (int j
=0;j
<n
;j
++){if (A
[i
][j
]){flag
=true
;A
[i
][j
]=2;dfs(A
,i
,j
,m
,n
);break;}}if (flag
) break;}return bfs(A
,m
,n
);}int d
[4][2]={0,1,1,0,0,-1,-1,0};queue
<pair
<int,int>> que
;
};
總結
以上是生活随笔為你收集整理的LeetCode 934 最短的桥的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
