Approach

Use DFS to find and mark all cells of the first island, adding their coordinates to a queue.
Use BFS from all marked cells, expanding outward and counting steps until a cell of the second island is reached.
Code

[{"language":"C++","code":"#include <vector>\n#include <queue>\nusing namespace std;\nclass Solution {\npublic:\n\tint shortestBridge(vector<vector<int>>& A) {\n\t\tint m = A.size(), n = A[0].size();\n\t\tvector<vector<bool>> vis(m, vector<bool>(n));\n\t\tqueue<pair<int,int>> q;\n\t\tint dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};\n\t\tbool found = false;\n\t\tauto dfs = [&](int i, int j, auto&& dfs_ref) -> void {\n\t\t\tif (i<0||j<0||i>=m||j>=n||vis[i][j]||A[i][j]==0) return;\n\t\t\tvis[i][j]=true; q.emplace(i,j);\n\t\t\tfor (auto& d : dirs) dfs_ref(i+d[0],j+d[1],dfs_ref);\n\t\t};\n\t\tfor (int i=0; i<m && !found; ++i)\n\t\t\tfor (int j=0; j<n && !found; ++j)\n\t\t\t\tif (A[i][j]==1) { dfs(i,j,dfs); found=true; }\n\t\tint step=0;\n\t\twhile (!q.empty()) {\n\t\t\tint sz=q.size();\n\t\t\twhile (sz--) {\n\t\t\t\tauto [x,y]=q.front(); q.pop();\n\t\t\t\tfor (auto& d : dirs) {\n\t\t\t\t\tint ni=x+d[0], nj=y+d[1];\n\t\t\t\t\tif (ni>=0&&nj>=0&&ni<m&&nj<n&&!vis[ni][nj]) {\n\t\t\t\t\t\tif (A[ni][nj]==1) return step;\n\t\t\t\t\t\tq.emplace(ni,nj); vis[ni][nj]=true;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\t++step;\n\t\t}\n\t\treturn -1;\n\t}\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;vector></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;queue></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">using</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> namespace</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> std</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tint</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> shortestBridge</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> A</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\t\tint</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> m </span><span style=\"color:#D73A49;--shiki-dark:#F97583\"
Related Tags
