Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- 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
- Output: 1
- Example 2:
- 11000
- 11000
- 00100
- 00011
- Output: 3
- Observations:
- - Diagonals are not considered connected islands for this version of the question
- - If grid is all zeros, than islands equals 0
- - If grid is all ones, than islands equals 1
- - The structure of a 2d grid of 1s and 0s is similar to that of a graph data structure, where nodes of an island are connected to 1 or more other nodes of the same island
- - For graphs, we can use Breath-First-Search algorithm to locate all the nodes in an island
- - We need an way to keep track of already visited nodes
- - Initially looks like 0(n) looks like best case scenerio since at least every node in the 2d matrix has to be visited once
- '''
- import random
- # input_matrix = [[0,0,1,1,0],
- # [1,0,0,0,1],
- # [1,1,1,1,1],
- # [0,0,0,0,0]] # 1
- def generate_matrix(size=5):
- # make sure there's a higher porpotion of ones to test call stack limitations
- return [[random.choice([1,0,1,0,1]) for x in range(size)] for y in range(size)]
- def pretty_print(matrix):
- print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in matrix]))
- # Attempt #1
- def locate_islands(input_matrix):
- row, col, islands = 0, 0, 0
- # pretty_print(input_matrix)
- for ir, row in enumerate(input_matrix):
- for ic, node in enumerate(row):
- if (node is 1):
- islands = islands + 1
- # print("starting node for BFS: {},{} is {}".format(ir, ic, node))
- bfs(ir, ic)
- print("output: ", islands)
- def bfs(ir, ic):
- # search to right, bottom, top, left of node
- if (input_matrix[ir][ic] is not 1):
- return 0
- input_matrix[ir][ic] = 2 # mark already visited with 2
- # print("Searching...", ic, ir)
- if (ir+1 < len(input_matrix)) and (input_matrix[ir+1][ic] is 1):
- bfs(ir+1, ic)
- if (ic+1 < len(input_matrix[ir])) and (input_matrix[ir][ic+1] is 1):
- bfs(ir, ic+1)
- if (ic-1 > 0) and (input_matrix[ir][ic-1] is 1):
- bfs(ir, ic-1)
- if (ir-1 > 0) and (input_matrix[ir-1][ic] is 1):
- bfs(ir-1, ic)
- return 0
- input_matrix = generate_matrix(size=5)
- locate_islands(input_matrix)
- # increase the size of grid
- input_matrix = generate_matrix(size=2000)
- # RecursionError: maximum recursion depth exceeded while calling a Python object
- print(len(input_matrix)) # stackoverflow error!
- locate_islands(input_matrix)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement