|
| 1 | +/** |
| 2 | + * In a given 2D binary array A, there are two islands. (An island is a 4-directionally |
| 3 | + * connected group of 1s not connected to any other 1s.) |
| 4 | + * |
| 5 | + * Now, we may change 0s to 1s so as to connect the two islands together to form 1 island. |
| 6 | + * |
| 7 | + * Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.) |
| 8 | + * |
| 9 | + * Example 1: |
| 10 | + * Input: [[0,1],[1,0]] |
| 11 | + * Output: 1 |
| 12 | + * |
| 13 | + * Example 2: |
| 14 | + * Input: [[0,1,0],[0,0,0],[0,0,1]] |
| 15 | + * Output: 2 |
| 16 | + * |
| 17 | + * Example 3: |
| 18 | + * Input: [[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]] |
| 19 | + * Output: 1 |
| 20 | + * |
| 21 | + * Note: |
| 22 | + * 1 <= A.length = A[0].length <= 100 |
| 23 | + * A[i][j] == 0 or A[i][j] == 1 |
| 24 | + */ |
| 25 | + |
| 26 | +publicclassShortestBridge934 { |
| 27 | +privateint[][]DIR =newint[][]{{0,1}, {0, -1}, {1,0}, {-1,0}}; |
| 28 | +publicintshortestBridge(int[][]A) { |
| 29 | +intm =A.length; |
| 30 | +intn =A[0].length; |
| 31 | +boolean[][]visited =newboolean[m][n]; |
| 32 | +Queue<int[]>edge =findOneIslandEdge(A,visited); |
| 33 | +intres =0; |
| 34 | +while (!edge.isEmpty()) { |
| 35 | +intlen =edge.size(); |
| 36 | +for (inti=0;i<len;i++) { |
| 37 | +int[]curr =edge.remove(); |
| 38 | +for (intk=0;k<4;k++) { |
| 39 | +intii =curr[0] +DIR[k][0]; |
| 40 | +intjj =curr[1] +DIR[k][1]; |
| 41 | +if (ii >=0 &&ii <m &&jj >=0 &&jj <n && !visited[ii][jj]) { |
| 42 | +if (A[ii][jj] ==0) { |
| 43 | +edge.add(newint[]{ii,jj}); |
| 44 | +visited[ii][jj] =true; |
| 45 | + }else { |
| 46 | +returnres; |
| 47 | + } |
| 48 | + } |
| 49 | + } |
| 50 | + } |
| 51 | +res++; |
| 52 | + } |
| 53 | +returnres; |
| 54 | + } |
| 55 | + |
| 56 | +privateQueue<int[]>findOneIslandEdge(int[][]A,boolean[][]visited) { |
| 57 | +intm =A.length; |
| 58 | +intn =A[0].length; |
| 59 | +for (inti=0;i<m;i++) { |
| 60 | +for (intj=0;j<n;j++) { |
| 61 | +if (A[i][j] ==1) { |
| 62 | +returncollectEdge(A,i,j,visited); |
| 63 | + } |
| 64 | + } |
| 65 | + } |
| 66 | +returnnull; |
| 67 | + } |
| 68 | + |
| 69 | +privateQueue<int[]>collectEdge(int[][]A,intsi,intsj,boolean[][]visited) { |
| 70 | +Queue<int[]>edge =newLinkedList<>(); |
| 71 | +Queue<int[]>q =newLinkedList<>(); |
| 72 | +intm =A.length; |
| 73 | +intn =A[0].length; |
| 74 | +visited[si][sj] =true; |
| 75 | +q.add(newint[]{si,sj}); |
| 76 | +while (!q.isEmpty()) { |
| 77 | +int[]curr =q.remove(); |
| 78 | +booleanisEdge =false; |
| 79 | +for (intk=0;k<4;k++) { |
| 80 | +intii =curr[0] +DIR[k][0]; |
| 81 | +intjj =curr[1] +DIR[k][1]; |
| 82 | +if (ii >=0 &&ii <m &&jj >=0 &&jj <n && !visited[ii][jj]) { |
| 83 | +if (A[ii][jj] ==0) { |
| 84 | +isEdge =true; |
| 85 | + }else { |
| 86 | +q.add(newint[]{ii,jj}); |
| 87 | +visited[ii][jj] =true; |
| 88 | + } |
| 89 | + } |
| 90 | + } |
| 91 | +if (isEdge) { |
| 92 | +edge.add(curr); |
| 93 | + } |
| 94 | + } |
| 95 | +returnedge; |
| 96 | + } |
| 97 | +} |