|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
| 3 | +importjava.util.LinkedList; |
| 4 | +importjava.util.Queue; |
| 5 | + |
3 | 6 | publicclass_463 { |
4 | 7 |
|
5 | 8 | publicstaticclassSolution1 { |
@@ -27,4 +30,46 @@ public int islandPerimeter(int[][] grid) { |
27 | 30 | returncount; |
28 | 31 | } |
29 | 32 | } |
| 33 | + |
| 34 | +publicstaticclassSolution2 { |
| 35 | +/** |
| 36 | + * My completely original solution on 10/4/2021: |
| 37 | + * Count the number of island neighbors that each island has, then reduce this number from four and add it to the result. |
| 38 | + */ |
| 39 | +publicintislandPerimeter(int[][]grid) { |
| 40 | +intperimeter =0; |
| 41 | +intm =grid.length; |
| 42 | +intn =grid[0].length; |
| 43 | +boolean[][]visited =newboolean[m][n]; |
| 44 | +int[]directions =newint[]{0,1,0, -1,0}; |
| 45 | +for (inti =0;i <m;i++) { |
| 46 | +for (intj =0;j <n;j++) { |
| 47 | +if (grid[i][j] ==1) { |
| 48 | +Queue<int[]>queue =newLinkedList<>(); |
| 49 | +queue.offer(newint[]{i,j}); |
| 50 | +while (!queue.isEmpty()) { |
| 51 | +int[]curr =queue.poll(); |
| 52 | +if (!visited[curr[0]][curr[1]]) { |
| 53 | +visited[curr[0]][curr[1]] =true; |
| 54 | +intneighborCount =0; |
| 55 | +for (intk =0;k <directions.length -1;k++) { |
| 56 | +intnewX =curr[0] +directions[k]; |
| 57 | +intnewY =curr[1] +directions[k +1]; |
| 58 | +if (newX >=0 &&newX <m &&newY >=0 &&newY <n &&grid[newX][newY] ==1) { |
| 59 | +neighborCount++; |
| 60 | +if (!visited[newX][newY]) { |
| 61 | +queue.offer(newint[]{newX,newY}); |
| 62 | + } |
| 63 | + } |
| 64 | + } |
| 65 | +perimeter +=4 -neighborCount; |
| 66 | + } |
| 67 | + } |
| 68 | +returnperimeter; |
| 69 | + } |
| 70 | + } |
| 71 | + } |
| 72 | +returnperimeter; |
| 73 | + } |
| 74 | + } |
30 | 75 | } |