2.py (1637B) [raw]
1 #!/usr/bin/env python3 2 import sys 3 4 def parse(): 5 G = [] 6 for l in sys.stdin: 7 G.append([c for c in l.strip()]) 8 return G 9 10 def cost(G): 11 def get(i, j): 12 if i < 0 or j < 0 or i >= len(G) or j >= len(G[0]): 13 return None 14 return G[i][j] 15 16 stk = [] 17 seen = set() 18 tot = 0 19 for i0 in range(len(G)): 20 for j0 in range(len(G[0])): 21 if (i0, j0) not in seen: 22 stk.append((i0, j0)) 23 # explore the plot 24 a = 0 25 p = 0 26 while stk: 27 (i, j) = stk.pop() 28 seen.add((i, j)) 29 crop = G[i][j] 30 a += 1 31 for n in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]: 32 if get(n[0],n[1]) == crop: 33 if n not in seen: 34 seen.add(n) 35 stk.append(n) 36 # unlike counting the perimeter, we count the 37 # _corners_ which is equivalent to the number of sides 38 for dy, dx in [(-1,-1),(-1,1),(1,-1),(1,1)]: 39 # outside corner is when both adjacent neighbors are diff 40 if get(i+dy,j) != crop and get(i,j+dx) != crop: 41 p += 1 42 # inside corner is when both adjacent neighbors are same but diag diff 43 elif get(i+dy,j) == crop and get(i,j+dx) == crop and get(i+dy,j+dx) != crop: 44 p += 1 45 # print((crop, i, j, a, p)) 46 tot += a*p 47 return tot 48 49 if __name__ == '__main__': 50 G = parse() 51 print(cost(G))