• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Sep 17th, 2019 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. 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.
3.
4. Example 1:
5.
6. 11110
7. 11010
8. 11000
9. 00000
10.
11. Output: 1
12.
13. Example 2:
14.
15. 11000
16. 11000
17. 00100
18. 00011
19.
20. Output: 3
21.
22. Observations:
23.
24. - Diagonals are not considered connected islands for this version of the question
25. - If grid is all zeros, than islands equals 0
26. - If grid is all ones, than islands equals 1
27.
28. - 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
29. - For graphs, we can use Breath-First-Search algorithm to locate all the nodes in an island
30. - We need an way to keep track of already visited nodes
31. - Initially looks like 0(n) looks like best case scenerio since at least every node in the 2d matrix has to be visited once
32. '''
33. import random
34.
35.
36. # input_matrix = [[0,0,1,1,0],
37. #                 [1,0,0,0,1],
38. #                 [1,1,1,1,1],
39. #                 [0,0,0,0,0]] # 1
40.
41. def generate_matrix(size=5):
42.     # make sure there's a higher porpotion of ones to test call stack limitations
43.     return [[random.choice([1,0,1,0,1]) for x in range(size)] for y in range(size)]
44.
45.
46. def pretty_print(matrix):
47.     print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in matrix]))
48.
49.
50. # Attempt #1
51. def locate_islands(input_matrix):
52.     row, col, islands = 0, 0, 0
53.     # pretty_print(input_matrix)
54.
55.     for ir, row in enumerate(input_matrix):
56.         for ic, node in enumerate(row):
57.             if (node is 1):
58.                 islands = islands + 1
59.                 # print("starting node for BFS: {},{} is {}".format(ir, ic, node))
60.                 bfs(ir, ic)
61.
62.     print("output: ", islands)
63.
64.
65.
66. def bfs(ir, ic):
67.     # search to right, bottom, top, left of node
68.     if (input_matrix[ir][ic] is not 1):
69.         return 0
70.
71.     input_matrix[ir][ic] = 2 # mark already visited with 2
72.
73.     # print("Searching...", ic, ir)
74.     if (ir+1 < len(input_matrix)) and (input_matrix[ir+1][ic] is 1):
75.         bfs(ir+1, ic)
76.
77.     if (ic+1 < len(input_matrix[ir])) and (input_matrix[ir][ic+1] is 1):
78.         bfs(ir, ic+1)
79.
80.     if (ic-1 > 0) and (input_matrix[ir][ic-1] is 1):
81.         bfs(ir, ic-1)
82.
83.     if (ir-1 > 0) and (input_matrix[ir-1][ic] is 1):
84.         bfs(ir-1, ic)
85.
86.     return 0
87.
88. input_matrix = generate_matrix(size=5)
89. locate_islands(input_matrix)
90.
91. # increase the size of grid
92. input_matrix = generate_matrix(size=2000)
93. # RecursionError: maximum recursion depth exceeded while calling a Python object
94. print(len(input_matrix)) # stackoverflow error!
95. locate_islands(input_matrix)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top