Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Problem: https://leetcode.com/problems/num
| 16 | * |
| 17 | */ |
| 18 | class NumberOfIslands { |
| 19 | |
| 20 | boolean[][] visited; |
| 21 | int r, c; |
| 22 | int islands; |
| 23 | |
| 24 | /** |
| 25 | * |
| 26 | * @param grid |
| 27 | * @return |
| 28 | */ |
| 29 | public int numIslands(char[][] grid) { |
| 30 | |
| 31 | if (grid == null || grid.length == 0) { |
| 32 | |
| 33 | return 0; |
| 34 | } |
| 35 | |
| 36 | r = grid.length; |
| 37 | c = grid[0].length; |
| 38 | islands = 0; |
| 39 | visited = new boolean[r][c]; |
| 40 | |
| 41 | for (int i = 0; i < r; i++) { |
| 42 | |
| 43 | for (int j = 0; j < c; j++) { |
| 44 | |
| 45 | if (grid[i][j] == '1' && !visited[i][j]) { |
| 46 | |
| 47 | _numIslands(grid, i, j); |
| 48 | islands++; |
| 49 | } |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | return islands; |
| 54 | } |
| 55 | |
| 56 | /** |
| 57 | * |
| 58 | * @param grid |
| 59 | * @param m |
| 60 | * @param n |
| 61 | */ |
| 62 | private void _numIslands(char[][] grid, int m, int n) { |
| 63 | |
| 64 | if (m < 0 || m >= r || n < 0 || n >= c || visited[m][n] || grid[m][n] == '0') { |
| 65 | |
| 66 | return; |
| 67 | } |
| 68 | |
| 69 | visited[m][n] = true; |
| 70 | |
| 71 | _numIslands(grid, m + 1, n); |
| 72 | _numIslands(grid, m, n + 1); |
| 73 | _numIslands(grid, m - 1, n); |
| 74 | _numIslands(grid, m, n - 1); |
| 75 | } |
nothing calls this directly
no outgoing calls
no test coverage detected