-
-
Save vgmoose/a15b7eab190abbf721ec to your computer and use it in GitHub Desktop.
| # initial island map | |
| bitmap = [ | |
| [0,0,1,1,0,0,0,1,0,0], | |
| [0,1,1,0,0,1,1,1,0,0], | |
| [0,1,0,0,0,0,0,0,0,0], | |
| [0,0,0,1,1,1,0,0,1,1], | |
| [0,0,0,0,1,1,1,1,1,0], | |
| [0,1,1,0,0,0,0,0,0,0] | |
| ] | |
| # get size and initialize count | |
| count = 0 | |
| height = len(bitmap) | |
| width = len(bitmap[0]) | |
| # create an empty copy of the grid with all Falses | |
| # we will use this to keep track of which nodes we have already | |
| # visited (and therefore, which islands we have already counted) | |
| visited = [[False]*width for x in range(0, height)] | |
| # this recursive function looks at all surrounding up, down, left, right | |
| # tiles and tries to visit them if they contain a land | |
| # (this algorithm is known as "FloodFill") | |
| def visitAll(x, y): | |
| # base case: we're at a water cell, or we've already visited this cell | |
| if not bitmap[x][y] or visited[x][y]: | |
| return | |
| # mark this cell as seen in our visited grid, so we know for later | |
| visited[x][y] = True | |
| # go through up, down, left, and right cells (abs(i) != abs(j)) means we won't hit | |
| # any of the diagonals, nor the center | |
| for i in range(-1, 2): | |
| for j in range(-1, 2): | |
| # also make sure that the new coordinate is actually in bounds | |
| # on the grid (not less than 0 or greater than width/height) | |
| if abs(i) != abs(j) and x+i>=0 and y+j>=0 and x+i<height and y+j<width: | |
| visitAll(x+i, y+j) | |
| # go through all cells in the grid and attempt to visit them | |
| # this will take O(N^2) runtime, but it won't waste time going | |
| # into any cells that we've already visited | |
| for x in range(0, height): | |
| for y in range(0, width): | |
| # already visited this one at an earlier run (via the recursive | |
| # function above), so skip it | |
| if visited[x][y]: | |
| continue | |
| # found a land cell! Increase our count, and mark its adjacent | |
| # cells as already visited as well | |
| if bitmap[x][y]: | |
| visitAll(x, y) | |
| count += 1 | |
| # print the total count, which only ever increased when we hit a "new" | |
| # land cell. Since visitAll visited all the neighboring land cells (aka an | |
| # island) and stopped us from double-counting any land cells, this value | |
| # is also the total amount of islands. | |
| print(count) |
Hi! I went through and added comments to the code. Also, I noticed there was an error with it... Thanks for asking so I could see that, and also sorry for that confusion. It's also important to note that this code uses the fact that 0 == False and 1 == True.
The error was that that checking x != y doesn't make sense. What this check should do instead is abs(i) != abs(j). This is how the fix looks in the code.
This approach to check four directions with a nested loop is not great. Doing for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]: is cleaner and easier to read, and avoids this bug.
Here's the above code on a similar leetcode question: https://leetcode.com/submissions/detail/671874157/
Using the array instead is a little faster: https://leetcode.com/submissions/detail/671876596/ (no wasted time visiting and skipping diagonals)
This approach still uses a lot of memory however, to store the whole visited copy of the grid. You can get around this by re-using the same variable (although, this will alter the input data. That could be undone after the count is obtained, if needed).
Re-using the original grid as the visited grid as well ("2" means visited, "0"=water, "1"=land): https://leetcode.com/submissions/detail/671879624
The main algorithm used here is Flood Fill, so at each cell of the grid it tries to visit the entire island and increase the island count, then tries to not revisited previously visited (counted) land cells.
To view the above leetcode links, you may need to sign in.
This is the similar question: https://leetcode.com/problems/number-of-islands/
hello sir, sorry to bother you, i found your code but i don't really understand, could you please explain step by step?