Friday, November 13, 2015

LeetCode [305] Number of Islands II

======================= =====================

Note:
    1. differentiate the islands by "id"
    2. "islands" records the total number of islands
    3, "state" records the ids of the islands
Example:  
 0  0  0  0
 0  0  0  0
 0  0  0  0
 0  0  0  0

step 1: [0, 1]
 0  1  0  0
 0  0  0  0
 0  0  0  0
 0  0  0  0
islands = 1

step 2: [1, 0]
 0  1  0  0
 2  0  0  0
 0  0  0  0
 0  0  0  0
islands = 2

step 3: [2, 1]
 0  1  0  0
 2  0  0  0
 0  3  0  0
 0  0  0  0
islands = 3

step 4: [1, 1]
at this step, id_t = 1, id_l = 2, id_b = 3 and id_r = 0
thus, id is set to the minimal minimum one, which is 1
since the new island (1,1) connects the other 3 existing islands
merge them into one island and update their ids accordingly
after step 4, "state" becomes:
 0  1  0  0
 1  1  0  0
 0  1  0  0
 0  0  0  0
islands = 1

the set "merged" is used to avoid cases like
 0  2  0  0  0
 2  2  0  1  0
 0  2  2  0  0
 0  0  0  0  0
 0  0  0  0  0
currently, there are two islands 1 and 2.
if a new land [1, 2] is created, both id_l and id_b is 2
but "islands" should be decreased once
so after [1,2] is created
the state becomes:
 0  1  0  0  0
 1  1  1  1  0
 0  1  1  0  0
 0  0  0  0  0
 0  0  0  0  0


 Ref
[1] https://leetcode.com/problems/number-of-islands-ii/
OJ
[2] https://leetcode.com/discuss/69572/easiest-java-solution-with-explanations

No comments:

Post a Comment