rahools

Untitled

Aug 5th, 2021
639
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #%%
  2. class Graph:
  3.  
  4.     def __init__(self, row, col, g):
  5.         self.ROW = row
  6.         self.COL = col
  7.         self.graph = g
  8.  
  9.     def isSafe(self, i, j, visited):
  10.         return (
  11.             i >= 0 and i < self.ROW
  12.             and j >= 0 and j < self.COL
  13.             and not visited[i][j]
  14.             and self.graph[i][j]
  15.         )
  16.              
  17.  
  18.     # A utility function to do DFS for a 2D
  19.     # boolean matrix. It only considers
  20.     # the 8 neighbours as adjacent vertices
  21.     def DFS(self, i, j, visited):
  22.  
  23.         # These arrays are used to get row and
  24.         # column numbers of 8 neighbours
  25.         # of a given cell
  26.         rowNbr = [-1, 0, 0,  1]
  27.         colNbr = [0, -1, 1, 0]
  28.          
  29.         # Mark this cell as visited
  30.         visited[i][j] = True
  31.  
  32.         # Recur for all connected neighbours
  33.         count = 1
  34.         for k in range(4):
  35.             if self.isSafe(i + rowNbr[k], j + colNbr[k], visited):
  36.                 count += self.DFS(i + rowNbr[k], j + colNbr[k], visited)
  37.  
  38.         return count
  39.  
  40.     def diagCheck(self, i, j):
  41.         rowNbr = [-1, 1, -1,  1]
  42.         colNbr = [1, -1, -1, 1]
  43.  
  44.         ans = True
  45.         for k in range(4):
  46.             if i >= 0 and i < self.ROW and j >= 0 and j < self.COL:
  47.                 ans = ans and self.graph[i + rowNbr[k]][j + colNbr[k]] == 0
  48.         return ans
  49.  
  50.  
  51.     # The main function that returns
  52.     # count of islands in a given boolean
  53.     # 2D matrix
  54.     def countIslands(self):
  55.         # Make a bool array to mark visited cells.
  56.         # Initially all cells are unvisited
  57.         visited = [[False for j in range(self.COL)]for i in range(self.ROW)]
  58.  
  59.         # Initialize count as 0 and traverse
  60.         # through the all cells of
  61.         # given matrix
  62.         count = 0
  63.         for i in range(self.ROW):
  64.             for j in range(self.COL):
  65.                 # If a cell with value 1 is not visited yet,
  66.                 # then new island found
  67.                 if visited[i][j] == False and self.graph[i][j] == 1:
  68.                     # Visit all cells in this island
  69.                     # and increment island count
  70.                     t = self.DFS(i, j, visited)
  71.                     if t > 1:
  72.                         count += 1
  73.                     else:
  74.                         if self.diagCheck(i, j):
  75.                             count += 1
  76.  
  77.         return count
  78.  
  79. #%%
  80. # graph = [[1, 1, 0, 0, 0],
  81. #         [0, 1, 0, 0, 1],
  82. #         [1, 0, 0, 1, 1],
  83. #         [0, 0, 0, 0, 0],
  84. #         [1, 0, 1, 0, 1]]
  85.  
  86. # graph = [
  87. #     [1, 0, 1, 1],
  88. #     [0, 0, 1, 0],
  89. #     [1, 0, 1, 1],
  90. #     [1, 0, 1, 0]
  91. # ]
  92.  
  93. graph = [
  94.     [1, 0, 0, 0, 0, 1, 1],
  95.     [0, 1, 0, 0, 0, 1, 0],
  96.     [0, 0, 1, 0, 0, 1, 1],
  97.     [1, 0, 0, 1, 0, 1, 1],
  98.     [1, 0, 0, 0, 0, 0, 0]
  99. ]
  100.  
  101. #%%
  102. row = len(graph)
  103. col = len(graph[0])
  104.  
  105. g = Graph(row, col, graph)
  106.  
  107. print("Number of islands is:")
  108. print(g.countIslands())
  109. # %%
  110.  
RAW Paste Data