from collections import defaultdict def solve(): file = "input.txt" grid = [] with open(file, 'r') as f: for line in f: grid.append(line.strip()) rows = len(grid) cols = len(grid[0]) def get_neighbors(r, c): neighbors = [] for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: neighbors.append((nr, nc)) return neighbors def bfs(r, c, char): q = [(r, c)] visited = set([(r, c)]) area = 0 perimeter = 0 while q: cr, cc = q.pop(0) area += 1 for nr, nc in get_neighbors(cr, cc): if (nr, nc) not in visited: if grid[nr][nc] == char: visited.add((nr, nc)) q.append((nr, nc)) else: perimeter += 1 return area, perimeter def bfs2(r, c, char): q = [(r, c)] visited = set([(r, c)]) area = 0 sides = 0 while q: cr, cc = q.pop(0) area += 1 ns = 0 for nr, nc in get_neighbors(cr, cc): if grid[nr][nc] != char: ns +=1 sides += ns for nr, nc in get_neighbors(cr, cc): if (nr, nc) not in visited and grid[nr][nc] == char: visited.add((nr, nc)) q.append((nr, nc)) return area, sides total_price = 0 visited = set() for r in range(rows): for c in range(cols): if (r, c) not in visited: char = grid[r][c] area, perimeter = bfs(r, c, char) total_price += area * perimeter for rr, cc in bfs(r,c, char)[2]: visited.add((rr,cc)) print(total_price) total_price2 = 0 visited = set() for r in range(rows): for c in range(cols): if (r, c) not in visited: char = grid[r][c] area, sides = bfs2(r, c, char) total_price2 += area * sides for rr, cc in bfs(r,c, char)[2]: visited.add((rr,cc)) print(total_price2) solve()