For reference purpose, I'll be jotting down my solutions to these problems here.
Following is an accepted quick solution to the Number of Islands problem (problem #200) on Leetcode. This solution implements it using the land "sinking" technique.
class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length==0) return 0; int islands = 0; for (int i=0; i<grid.length; i++) { for (int j=0; j<grid[i].length; j++) { if (grid[i][j] == '1') { islands += dfs(grid, i, j); } } } return islands; } int dfs(char[][] grid, int i, int j) { if (i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0') { return 0; } //sink grid[i][j] = '0'; dfs(grid, i+1, j); dfs(grid, i, j+1); dfs(grid, i-1, j); dfs(grid, i, j-1); return 1; } }
No comments:
Post a Comment