Number of Islands

Leave a comment

October 30, 2016 by oneOokay

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.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3


典型的DFS, easy 模式:

main method 里面 loop through整个岛屿,遇到’1′,count ++, 然后DFS把与当前’1’相连的所有’1’都消除掉. 接着继续loop.

一个int[][] dir来帮助 recursion

dfs一开始就可以开始进行filter return.

看看以前写的到现在一次性过终于有了一点点成就感啊…


二刷整体思想ok,但是清除岛屿没有写出来,用了四个while loop,实际上是错误的,应该用recursive。


Oct 30

这不看答案根本写不出来好吗

我的想法:

1. dp肯定行不通,放弃. 必须全部的scan。

2.想到能够找出每一个岛的边缘,但是也没什么用,按每个边缘去寻找海洋岛屿不切实际,边太大了。想不到接下去的办法。

3.看答案:答案其实就是把每一个岛屿转换成一个单个的1,这样消除了岛屿的所有其他土地,就不存在分辨边缘的问题。所以当接下来继续scan找到另一个1的时候,意味着这是另一个岛屿的边界,所以岛屿数+1.接着对这个新的岛屿进行消除。time complexity为grid mXn

private int row = 0, col = 0;
 public int numIslands(char[][] grid) {
 //go through the island, when == 1, count ++ and destroy it
 if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
 row = grid.length;
 col = grid[0].length;
 int count = 0;
 for(int i = 0; i < row; i ++){
 for (int j = 0; j < col; j ++){
 if (grid[i][j] == '1'){
 count ++;
 expand(grid, i, j);
 }
 }
 }
 return count;
 }
 static private int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 private void expand(char[][] grid, int i, int j){
 if(i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == '0') return;
 grid[i][j] = '0';
 for(int[] dir : dirs){
 expand(grid, i + dir[0], j + dir[1]);
 }
 }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: