Advertisement
viligen

areas_in_matrix_dfs

Aug 9th, 2022
520
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.00 KB | None | 0 0
  1. rows = int(input())
  2. cols = int(input())
  3.  
  4. matrix = [list(input()) for _ in range(rows)]
  5. visited = [[False] * cols for _ in range(rows)]
  6.  
  7.  
  8. def dfs(parent, row, col, matrix, visited):
  9.     if row < 0 or col < 0 or row >= len(matrix) or col >= len(matrix[0]):
  10.         return
  11.     if visited[row][col]:
  12.         return
  13.     if matrix[row][col] != parent:
  14.         return
  15.  
  16.     visited[row][col] = True
  17.     dfs(parent, row - 1, col, matrix, visited)
  18.     dfs(parent, row + 1, col, matrix, visited)
  19.     dfs(parent, row, col + 1, matrix, visited)
  20.     dfs(parent, row, col - 1, matrix, visited)
  21.  
  22.  
  23. area = {}
  24. total_areas = 0
  25. for r in range(rows):
  26.     for c in range(cols):
  27.         if visited[r][c]:
  28.             continue
  29.         key = matrix[r][c]
  30.         dfs(key, r, c, matrix, visited)
  31.         if key not in area:
  32.             area[key] = 0
  33.         area[key] += 1
  34.         total_areas += 1
  35.  
  36. print(f'Areas: {total_areas}')
  37. for letter, count in sorted(area.items()):
  38.     print(f"Letter '{letter}' -> {count}")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement