Advertisement
SetKaung

This Should Works

Sep 27th, 2024
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.41 KB | None | 0 0
  1. from disjointsets3 import DisjointSets
  2. import time
  3.  
  4.  
  5. def get_neighbors(x, y, image):
  6.     neighbors = []
  7.     if ((x-1) in range(M)) and image[x-1][y] == 1:
  8.         neighbors.append(((x-1)*N)+y)
  9.     if ((x+1) in range(M)) and image[x+1][y] == 1:
  10.         neighbors.append(((x+1)*N)+y)
  11.     if ((y-1) in range(N)) and image[x][y-1] == 1:
  12.         neighbors.append((x*N)+(y-1))
  13.     if ((y+1) in range(N)) and image[x][y+1] == 1:
  14.         neighbors.append((x*N)+(y+1))
  15.  
  16.     return neighbors
  17.  
  18.  
  19. st = time.process_time()
  20. M, N = map(int, input().split())
  21. image = [list(map(int, input().split())) for _ in range(M)]
  22. S = DisjointSets(M*N)
  23. clouds = []
  24.  
  25. for x in range(len(image)):
  26.     for y in range(len(image[x])):
  27.         if image[x][y] == 1:
  28.             coordinate = (x*N)+y
  29.             clouds.append(coordinate)
  30.             neighbors = get_neighbors(x, y, image)
  31.             for n in neighbors:
  32.                 S.union(coordinate, n)
  33.  
  34. et = time.process_time()
  35. print(et - st)
  36. sizes = {}
  37. largest = 0
  38.  
  39.  
  40. for current_row in range(M):
  41.     for current_column in range(N):
  42.         if image[current_row][current_column] == 1:
  43.             representative = S.findset(current_row*N+current_column)
  44.             if representative in sizes:
  45.                 sizes[representative] += 1
  46.             else:
  47.                 sizes[representative] = 1
  48.             largest = max(sizes[representative],largest)
  49.  
  50. print(largest)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement