{"id":"c02d9038-110a-4e05-b641-a96ae832b3cb","name":"Shortest Bridge","description":"In a given 2D binary array grid, there are two islands. Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.\r\nReturn the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain n numbers containing either 0 or 1.","outputFormat":"Return the smallest number of 0s that must be flipped.","constraints":"1&lt;= n &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint shortestBridge(vector<vector<int>>&v1)\n{\n \n}\n\nint main()\n{\n int n;cin>>n;\n vector<vector<int>> v1(n,vector<int>(n));\n for(int i=0;i<n;++i)\n {\n for(int j=0;j<n;++j) cin>>v1[i][j];\n }\n cout<<shortestBridge(v1);\n return 0;\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\npublic class Main {\n\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n int n = Integer.parseInt(br.readLine());\n int[][] arr = new int[n][n];\n\n for (int i = 0; i < n; i++) {\n String[] st = br.readLine().split(\" \");\n for (int j = 0; j < n; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n System.out.println(shortestBridge(arr));\n\n }\n \n \n public static int shortestBridge(int[][] arr) {\n \n \n } \n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n0 1 0\r\n0 0 0\r\n1 1 1\r\n","sampleOutput":"1\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"5ce6d4a1-b07f-4c2a-ba2e-ae4b54257ae4","name":"Shortest Bridge","slug":"shortest-bridge","type":1}],"next":{"id":"1b4900b5-71e2-4ec2-b751-648149767d81","name":"Shortest Bridge MCQ","type":0,"slug":"shortest-bridge-mcq"},"prev":{"id":"70e442d0-424b-466c-a9d6-77203298e3bc","name":"Kill the Most Monsters","type":0,"slug":"kill-the-most-monsters"}}}

Shortest Bridge

In a given 2D binary array grid, there are two islands. Now, we may change 0s to 1s so as to connect the two islands together to form 1 island. Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

{"id":"c02d9038-110a-4e05-b641-a96ae832b3cb","name":"Shortest Bridge","description":"In a given 2D binary array grid, there are two islands. Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.\r\nReturn the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain n numbers containing either 0 or 1.","outputFormat":"Return the smallest number of 0s that must be flipped.","constraints":"1&lt;= n &lt;= 1000","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint shortestBridge(vector<vector<int>>&v1)\n{\n \n}\n\nint main()\n{\n int n;cin>>n;\n vector<vector<int>> v1(n,vector<int>(n));\n for(int i=0;i<n;++i)\n {\n for(int j=0;j<n;++j) cin>>v1[i][j];\n }\n cout<<shortestBridge(v1);\n return 0;\n}"},"java":{"code":"import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.*;\n\npublic class Main {\n\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n int n = Integer.parseInt(br.readLine());\n int[][] arr = new int[n][n];\n\n for (int i = 0; i < n; i++) {\n String[] st = br.readLine().split(\" \");\n for (int j = 0; j < n; j++) {\n arr[i][j] = Integer.parseInt(st[j]);\n }\n }\n\n System.out.println(shortestBridge(arr));\n\n }\n \n \n public static int shortestBridge(int[][] arr) {\n \n \n } \n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n0 1 0\r\n0 0 0\r\n1 1 1\r\n","sampleOutput":"1\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"5ce6d4a1-b07f-4c2a-ba2e-ae4b54257ae4","name":"Shortest Bridge","slug":"shortest-bridge","type":1}],"next":{"id":"1b4900b5-71e2-4ec2-b751-648149767d81","name":"Shortest Bridge MCQ","type":0,"slug":"shortest-bridge-mcq"},"prev":{"id":"70e442d0-424b-466c-a9d6-77203298e3bc","name":"Kill the Most Monsters","type":0,"slug":"kill-the-most-monsters"}}}
plane

Editor

Loading...

Shortest Bridge

easy

In a given 2D binary array grid, there are two islands. Now, we may change 0s to 1s so as to connect the two islands together to form 1 island. Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Constraints

1<= n <= 1000

Format

Input

First line contains an integer n. Each of next n lines contain n numbers containing either 0 or 1.

Output

Return the smallest number of 0s that must be flipped.

Example

Sample Input

3 0 1 0 0 0 0 1 1 1

Sample Output

1

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode