Advertisement
SetKaung

LargestCloud

Sep 27th, 2024
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.64 KB | None | 0 0
  1. # Name: Set Kaung Lwin
  2. # ID: 6632017
  3. # Sec: 543
  4.  
  5.  
  6. rows,columns = map(int,input().split())
  7.  
  8. image = [[] for _ in range(rows)]
  9.  
  10. for current_row in range(len(image)):
  11.     image[current_row] = list(map(int,input().split()))
  12.  
  13. from disjointsets3 import DisjointSets
  14. def printImage(m):
  15.     for i in m:
  16.         print(i)
  17.  
  18. moves =[(-1,0),(1,0),(0,1),(0,-1)] # up down right left
  19.  
  20. def isValid(tr,tc):
  21.     return tr >= 0 and tr < rows and tc >=0 and tc < columns
  22.  
  23. def sides(r,c):
  24.     valid_moves = []
  25.     for (i,j) in moves:
  26.         target_row = r+i
  27.         target_column = c+j
  28.         if isValid(target_row,target_column):
  29.             valid_moves.append((target_row,target_column))
  30.  
  31.     return valid_moves
  32.  
  33.  
  34.  
  35.  
  36. ds = DisjointSets(rows*columns)
  37.  
  38.  
  39. largest = 0
  40.  
  41. for current_row in range(len(image)):
  42.     for current_column in range(len(image[current_row])):
  43.         if image[current_row][current_column] == 1:
  44.             for (neighbor_row,neighbor_col) in sides(current_row,current_column):
  45.                 if image[neighbor_row][neighbor_col] == 1:
  46.                     ds.union( ( neighbor_row*columns+neighbor_col ) , ( current_row*columns+current_column ) )
  47.  
  48. sizes = {}    
  49.        
  50. for current_row in range(rows):
  51.     for current_column in range(columns):
  52.         if image[current_row][current_column] == 1:
  53.             representative = ds.findset(current_row*columns+current_column)
  54.             if representative in sizes:
  55.                 sizes[representative] += 1
  56.             else:
  57.                 sizes[representative] = 1
  58.             largest = max(sizes[representative],largest)
  59.  
  60. print(largest)
  61.                
  62.  
  63.  
  64.  
  65.  
  66.  
  67.    
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement