Spaces:
Running
Running
File size: 2,367 Bytes
a4da721 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
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() |