=======================
=====================
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
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