|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +/** |
| 4 | + * Created by fishercoder1534 on 9/29/16. |
| 5 | + */ |
| 6 | +publicclassNumberofIslands { |
| 7 | + |
| 8 | + |
| 9 | +publicstaticintnumIslands(char[][]grid) { |
| 10 | +if(grid ==null ||grid.length ==0)return0; |
| 11 | +intcount =0; |
| 12 | +intm =grid.length,n =grid[0].length; |
| 13 | +for(inti =0;i <m;i++){ |
| 14 | +for(intj =0;j <n;j++){ |
| 15 | +if(grid[i][j] =='1'){ |
| 16 | +count++; |
| 17 | +dfs(grid,i,j,m,n); |
| 18 | + } |
| 19 | + } |
| 20 | + } |
| 21 | +returncount; |
| 22 | + } |
| 23 | + |
| 24 | +staticvoiddfs(char[][]grid,inti,intj,intm,intn){ |
| 25 | +if(i <0 ||i >=m ||j <0 ||j >=n ||grid[i][j] =='0')return; |
| 26 | +grid[i][j] ='0'; |
| 27 | +dfs(grid,i+1,j,m,n); |
| 28 | +dfs(grid,i,j+1,m,n); |
| 29 | +dfs(grid,i-1,j,m,n); |
| 30 | +dfs(grid,i,j-1,m,n); |
| 31 | + } |
| 32 | + |
| 33 | + |
| 34 | +publicstaticvoidmain(String...args){ |
| 35 | +// char[][] grid = new char[][]{ |
| 36 | +// {'1','1','1','1','0'}, |
| 37 | +// {'1','1','0','1','0'}, |
| 38 | +// {'1','1','0','0','0'}, |
| 39 | +// {'0','0','0','0','0'}, |
| 40 | +// }; |
| 41 | + |
| 42 | +// ["11000","11000","00100","00011"] |
| 43 | +// char[][] grid = new char[][]{ |
| 44 | +// {'1','1','0','0','0'}, |
| 45 | +// {'1','1','0','0','0'}, |
| 46 | +// {'0','0','1','0','0'}, |
| 47 | +// {'0','0','0','1','1'}, |
| 48 | +// }; |
| 49 | + |
| 50 | +// ["111","010","111"] |
| 51 | +//doing normal row by row and column by column scan will fail by this test case: |
| 52 | +//when encountering grid[2][0], grid[2][1] hasn't been marked to '#' yet, so, it'll count grid[2][0] as a new island, which |
| 53 | +//in fact it is not! |
| 54 | +//So, we must apply DFS, so how does Union Find work? |
| 55 | +char[][]grid =newchar[][]{ |
| 56 | + {'1','1','1'}, |
| 57 | + {'0','1','0'}, |
| 58 | + {'1','1','1'}, |
| 59 | + }; |
| 60 | +System.out.println(numIslands(grid)); |
| 61 | + } |
| 62 | +} |