Problem:
 Score : 300 points    Problem Statement There is a grid with H rows and W columns, where each square is painted black or white.  You are given H strings S_1, S_2, ..., S_H , each of length W .
If the square at the i -th row from the top and the j -th column from the left is painted black, the j -th character in the string S_i is # ; if that square is painted white, the j -th character in the string S_i is . .  Find the number of pairs of a black square c_1 and a white square c_2 that satisfy the following condition:   There is a path from the square c_1 to the square c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...       Constraints  1 \leq H, W \leq 400  |S_i| = W ( 1 \leq i \leq H )  For each i ( 1 \leq i \leq H ), the string S_i consists of characters # and . .         Input Input is given from Standard Input in the following format:  H  W  S_1  S_2  :  S_H       Output Print the answer.        Sample Input 1 3 3
.#.
..#
#..      Sample Output 1 10  Some of the pairs satisfying the condition are ((1, 2), (3, 3)) and ((3, 1), (3, 2)) , where (i, j) denotes the square at the i -th row from the top and the j -th column from the left.       Sample Input 2 2 4
....
....      Sample Output 2 0       Sample Input 3 4 3
###
###
...
###      Sample Output 3 6

Solution (Python):

class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

def conv(i, j):
    return (i-1)*W + j-1

H, W = map(int, input().split())
Sss = ['_' + input() + '_' for _ in range(H)]
Sss = ['_' * (W + 2)] + Sss + ['_' * (W + 2)]

N = H * W
UF = UnionFind(N)
for i in range(1, H+1):
    for j in range(1, W+1):
        revS = '.' if Sss[i][j] == '
        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            if Sss[i+di][j+dj] == revS:
                UF.union(conv(i, j), conv(i+di, j+dj))

numBs, numWs = [0]*N, [0]*N
for i in range(1, H+1):
    for j in range(1, W+1):
        no = UF.find(conv(i, j))
        if Sss[i][j] == '
            numBs[no] += 1
        else:
            numWs[no] += 1

ans = 0
for numB, numW in zip(numBs, numWs):
    ans += numB * numW
print(ans)

Solution (Python):

from collections import deque

H, W = map(int, input().split())

S_list = [list(input()) for _ in range(H)]
bw = [0]*(H*W)
visited = [0]*(H*W)

G = dict()


vid = 0
for i in range(H):
    for j in range(W):
        G[vid] = dict()
        if i > 0:
            if S_list[i][j] != S_list[i-1][j]:
                G[vid][vid-W] = 1
        if i < H-1:
            if S_list[i][j] != S_list[i+1][j]:
                G[vid][vid+W] = 1
        if j > 0:
            if S_list[i][j] != S_list[i][j-1]:
                G[vid][vid-1] = 1
        if j < W-1:
            if S_list[i][j] != S_list[i][j+1]:
                G[vid][vid+1] = 1
        if S_list[i][j] == "
            bw[vid] = 1
        vid += 1


res = 0



for st in range(H*W):
    
    if visited[st] == 1:
        continue
    
    queue = deque()
    queue.append(st)
    visited[st] = 1
    res_temp = 0
    res_temp_black = 0

    while len(queue) > 0:
        s = queue.popleft()
        res_temp += 1
        if bw[s] == 1:
            res_temp_black += 1
        for t in G[s].keys():
            if visited[t] == 0:
                visited[t] = 1
                queue.append(t)
    res += res_temp_black*(res_temp-res_temp_black)

print(res)

Solution (Python):
import collections
import itertools
import operator

H, W = (int(i) for i in input().split())
S = []
for i in range(H):
    S.append(input())

v = []
for i in range(H*W):
    hh = i//W
    ww = i % W
    v.append(S[hh][ww])

class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

tree = UnionFind()
for i in range(H):
    for j in range(W-1):
        if S[i][j] != S[i][j+1]:
            tree.unite((i,j),(i,j+1))

for i in range(W):
    for j in range(H-1):
        if S[j][i] != S[j+1][i]:
            tree.unite((j,i),(j+1,i))

a = list(tree.grouper())
res = 0
for lis in a:
    br = 0
    wt = 0
    for po in lis:
        if S[po[0]][po[1]] == ".":
            wt += 1
        else:
            br += 1
    res += wt * br

print(res)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
visit=[[False]*W for i in range(H)]
par=[[None]*W for i in range(H)]
dd={}
X=[-1,0,1,0]
Y=[0,-1,0,1]
for j in range(H):
    for i in range(W):
        if visit[j][i]:
            continue
        if S[j][i]=='.':
            continue
        lH=deque()
        lH.append((j,i,0))
        par[j][i]=(i,j)
        num=0
        while lH:
            y,x,t=lH.popleft()
            visit[y][x]=True
            for k in range(4):
                nx=x+X[k]
                ny=y+Y[k]
                if 0<=nx<W and 0<=ny<H:
                    if visit[ny][nx]:
                        continue
                    if t==0 and S[ny][nx]=='.':
                        visit[ny][nx]=True
                        num+=1
                        lH.append((ny,nx,1))
                    elif t==1 and S[ny][nx]=='
                        visit[ny][nx] = True
                        par[ny][nx]=(i,j)
                        lH.append((ny,nx,0))
        dd[(i,j)]=num


ans=0
for j in range(H):
    for i in range(W):
        if S[j][i]=='
            x,y=par[j][i]
            ans+=dd[(x,y)]
print(ans)

Solution (Python):
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
H, W = inpl()
G = []

class UnionFindTree():
    
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
  
    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i]) 
            self.parent[i] = group
        return group
      
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]: 
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px
                
            self.parent[py] = px
            self.size[px] += self.size[py]
    
    def getsize(self, x):
        return self.size[self.find(x)]


def binarize(h, w):
    return h*W + w

def reverse(g):
    h, w = divmod(g, W)
    return h, w

UFT = UnionFindTree(H*W)

for _ in range(H):
    G.append(input())

for h in range(H-1):
    for w in range(W):
        if G[h][w] != G[h+1][w]:
            UFT.unite(binarize(h, w),
                      binarize(h+1, w))

for h in range(H):
    for w in range(W-1):
        if G[h][w] != G[h][w+1]:
            UFT.unite(binarize(h, w),
                      binarize(h, w+1))

D = defaultdict(lambda: [0, 0])
for i in range(H*W):
    h, w = reverse(i)
    D[UFT.find(i)][G[h][w] == "."] += 1

ans = 0
for k, v in D.items():
    ans += v[0] * v[1]

print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w = li()
inp = [lc() for _ in range(h)]
grid = [[-1]*w for _ in range(h)]
for i, row in enumerate(inp):
    for j, col in enumerate(row):
        if inp[i][j] == ".":
            grid[i][j] = 0
        else:
            grid[i][j] = 1

dis = [-1, 0, 1, 0]
djs = [0, -1, 0, 1]
hasVisited = [[False]*w for _ in range(h)]

def dfs(sti, stj, h, w):
    stack = [(sti, stj)]
    cnt_white = 0
    cnt_black = 0
    while stack:
        i,j = stack.pop()
        for di, dj in zip(dis, djs):
            if 0 <= i+di < h and 0 <= j+dj < w:
                if (not hasVisited[i+di][j+dj]) and (grid[i+di][j+dj] != grid[i][j]):
                    hasVisited[i+di][j+dj] = True
                    if grid[i+di][j+dj] == 0:
                        cnt_white += 1
                    else:
                        cnt_black += 1
                    stack.append((i+di, j+dj))
               
    return cnt_white * cnt_black

ans = 0
for r in range(h):
    for c in range(w):
        if hasVisited[r][c]:
            continue
        
        cnt = dfs(r,c,h,w)
        ans += cnt
        
print(ans)

Solution (Python):
from collections import Counter

H,W = map(int,input().split())
S = [input() for i in range(H)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if j < W-1 and S[i][j] != S[i][j+1]:
            uf.unite(i*W+j, i*W+j+1)
        if i < H-1 and S[i][j] != S[i+1][j]:
            uf.unite(i*W+j, (i+1)*W+j)
for i in range(H*W):
    uf.root(i)

c1 = Counter()
c2 = Counter()

for i in range(H):
    for j in range(W):
        k = i*W+j
        if S[i][j] == '.':
            c1[uf.root(k)] += 1
        else:
            c2[uf.root(k)] += 1

ans = 0
for k in c1.keys():
    ans += c1[k] * c2[k]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

ans = 0

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

was = [[0 for i in range(w)] for j in range(h)]

def dfs(x, y):
    global cc
    global was
    was[x][y] = 1
    if s[x][y] == '
        cc[1] += 1
    else:
        cc[0] += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and ny >= 0 and nx < h and ny < w and s[nx][ny] != s[x][y] and not was[nx][ny]:
            dfs(nx, ny)

for i in range(h):
    for j in range(w):
        if not was[i][j]:
            cc = [0] * 2
            dfs(i, j)
            ans += cc[1] * cc[0]
print(ans)

Solution (Python):
h, w = list(map(int, input().split()))
sss = ['x' * (w + 2)] + list('x' + input() + 'x' for _ in range(h)) + ['x' * (w + 2)]
checked = [[False] * (w + 2) for _ in range(h + 2)]
ans = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def dfs(i, j):
    w_cnt, b_cnt = 0, 0
    q = [(i, j, sss[i][j] == '.')]
    while q:
        y, x, is_white = q.pop()
        if checked[y][x]:
            continue
        checked[y][x] = True
        if is_white:
            w_cnt += 1
        else:
            b_cnt += 1

        for di, dj in move:
            ni = y + di
            nj = x + dj
            if checked[ni][nj]:
                continue
            nc = sss[ni][nj]
            if nc == 'x':
                continue
            elif (nc == '.') == is_white:
                continue
            else:
                q.append((ni, nj, nc == '.'))
    return w_cnt * b_cnt


for i in range(1, h + 1):
    for j in range(1, w + 1):
        if checked[i][j]:
            continue
        ans += dfs(i, j)
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
index = ".
S = [list(map(index, input())) for i in range(H)]

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))

used = [[0]*W for i in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if used[i][j]:
            continue
        que = deque([(i, j)])
        used[i][j] = 1
        C = [0, 0]
        C[S[i][j]] += 1
        f = ((i + j) & 1) ^ S[i][j]
        while que:
            x, y = que.popleft()
            s = ((x + y) & 1) ^ 1
            for dx, dy in dd:
                nx = x + dx; ny = y + dy
                if not 0 <= nx < H or not 0 <= ny < W or used[nx][ny] or (s ^ S[nx][ny]) != f:
                    continue
                que.append((nx, ny))
                used[nx][ny] = 1
                C[S[nx][ny]] += 1
        ans += C[0] * C[1]
print(ans)