Recently, I've solved this "Number of Islands" problem on LeetCode, the solution was accepted by the LeetCode OJ.
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.
A single island:
11110 11010 11000 00000
11000 11000 00100 00011
The idea behind the solution posted below is to:
- iterate over every cell of the grid
- when find a
1value, increment the island counter, use the BFS to find all cells in the current island
- mark all the cells in the current island with value
from collections import deque class Solution(object): def append_if(self, queue, x, y): """Append to the queue only if in bounds of the grid and the cell value is 1.""" if 0 <= x < len(self.grid) and 0 <= y < len(self.grid): if self.grid[x][y] == '1': queue.append((x, y)) def mark_neighbors(self, row, col): """Mark all the cells in the current island with value = 2. Breadth-first search.""" queue = deque() queue.append((row, col)) while queue: x, y = queue.pop() self.grid[x][y] = '2' self.append_if(queue, x - 1, y) self.append_if(queue, x, y - 1) self.append_if(queue, x + 1, y) self.append_if(queue, x, y + 1) def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ if not grid or len(grid) == 0 or len(grid) == 0: return 0 self.grid = grid row_length = len(grid) col_length = len(grid) island_counter = 0 for row in range(row_length): for col in range(col_length): if self.grid[row][col] == '1': # found an island island_counter += 1 self.mark_neighbors(row, col) return island_counter if __name__ == '__main__': grid = """11000 11000 00100 00011""" grid = [list(line) for line in grid.splitlines()] print(Solution().numIslands(grid))
Is it the most optimal solution to the problem, or is there a more efficient approach? What would you improve code-quality or code-organization wise?