Spaces:
Running
Running
| 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() |