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



Sample input:
3 3
.#.
..#
#..


Sample output:
10

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = []
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if (a,b) in visited:
                continue
            visited.append((a,b))
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:56 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:41 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 18:42:51 2018

@author: Owner
"""

#import collections
#import scipy.misc
#import sys
import numpy as np
#import math
#from operator import itemgetter
#import itertools
#素因数を並べる
"""
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')

def main():
    

if __name__ == '__main__':
    main()

"""

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

S = [input() for h in range(H)] 


def main():
    l_opn = []
    l_cls = list(range(H*W))
    #print(l_cls)
    result = 0
    n=0
    h=0
    w=0
    nb=0
    nw=0
    flag_next = True
    while l_cls:
        cnt_opn = 0
        if flag_next:                
            l_opn.append(l_cls.pop(0))
            n = l_opn[0]
            h = n % H
            w = n // H
            if (S[h][w] == "#"):
                nb +=1
            else:
                nw +=1
            
        n = l_opn.pop(0)
        h = n % H
        w = n // H
                
        if (w > 0)  and (S[h][w-1] != S[h][w]):
            if (n-H) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n-H)))
                if (S[h][w-1] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1
            else:
                pass
        else:
            pass
            
        if (h > 0) and (S[h-1][w] != S[h][w]):
            if (n-1) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n-1)))
                if (S[h-1][w] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1         
            else:
                pass
        else:
            pass
        
        if (h < H-1) and (S[h+1][w] != S[h][w]):
            if (n+1) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n+1)))
                if (S[h+1][w] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1  
            else:
                pass
        else:
            pass    
                
        if (w < W-1) and (S[h][w+1] != S[h][w]):
            if (n+H) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n+H)))
                if (S[h][w+1] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1
            else:
                pass
        else:
            pass                  
        if cnt_opn == 0 and (not l_opn):
            result += nb*nw
            #print(result)
            n=0
            nb=0
            nw=0
            #print("cls: "+str(l_cls))
            l_opn = []
            flag_next = True
        else:
            
            #print("opn: "+str(l_opn))
            flag_next = False
            pass
    result += nb*nw    
    print(result)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:56 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:41 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 18:42:51 2018

@author: Owner
"""

#import collections
#import scipy.misc
#import sys
import numpy as np
#import math
#from operator import itemgetter
#import itertools
#素因数を並べる
"""
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')

def main():
    

if __name__ == '__main__':
    main()

"""

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

S = [input() for h in range(H)] 


def main():
    l_opn = []
    l_cls = list(range(H*W))
    #print(l_cls)
    result = 0
    n=0
    h=0
    w=0
    nb=0
    nw=0
    flag_next = True
    while len(l_cls) != 0:
        cnt_opn = 0
        if flag_next:                
            l_opn.append(l_cls.pop(0))
            n = l_opn[0]
            h = n % H
            w = n // H
            if (S[h][w] == "#"):
                nb +=1
            else:
                nw +=1
            
        n = l_opn.pop(0)
        h = n % H
        w = n // H
                
        if (w > 0)  and (S[h][w-1] != S[h][w]):
            if (n-H) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n-H)))
                if (S[h][w-1] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1
            else:
                pass
        else:
            pass
            
        if (h > 0) and (S[h-1][w] != S[h][w]):
            if (n-1) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n-1)))
                if (S[h-1][w] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1         
            else:
                pass
        else:
            pass
        
        if (h < H-1) and (S[h+1][w] != S[h][w]):
            if (n+1) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n+1)))
                if (S[h+1][w] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1  
            else:
                pass
        else:
            pass    
                
        if (w < W-1) and (S[h][w+1] != S[h][w]):
            if (n+H) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n+H)))
                if (S[h][w+1] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1
            else:
                pass
        else:
            pass                  
        if cnt_opn == 0 and len(l_opn) == 0:
            result += nb*nw
            #print(result)
            n=0
            nb=0
            nw=0
            #print("cls: "+str(l_cls))
            l_opn = []
            flag_next = True
        else:
            
            #print("opn: "+str(l_opn))
            flag_next = False
            pass
    result += nb*nw    
    print(result)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:56 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:41 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 18:42:51 2018

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')

def main():
    

if __name__ == '__main__':
    main()

"""

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

S = [input() for h in range(H)] 


def main():
    l_opn = []
    l_cls = list(range(H*W))
    #print(l_cls)
    result = 0
    n=0
    h=0
    w=0
    nb=0
    nw=0
    flag_next = True
    while len(l_cls) != 0:
        cnt_opn = 0
        if flag_next:                
            l_opn.append(l_cls.pop(0))
            n = l_opn[0]
            h = n % H
            w = n // H
            if (S[h][w] == "#"):
                nb +=1
            else:
                nw +=1
            
        n = l_opn.pop(0)
        h = n % H
        w = n // H
                
        if (w > 0)  and (S[h][w-1] != S[h][w]):
            if (n-H) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n-H)))
                if (S[h][w-1] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1
            else:
                pass
        else:
            pass
            
        if (h > 0) and (S[h-1][w] != S[h][w]):
            if (n-1) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n-1)))
                if (S[h-1][w] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1         
            else:
                pass
        else:
            pass
        
        if (h < H-1) and (S[h+1][w] != S[h][w]):
            if (n+1) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n+1)))
                if (S[h+1][w] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1  
            else:
                pass
        else:
            pass    
                
        if (w < W-1) and (S[h][w+1] != S[h][w]):
            if (n+H) in l_cls:
                l_opn.append(l_cls.pop(l_cls.index(n+H)))
                if (S[h][w+1] == "#"):
                    nb +=1
                else:
                    nw +=1
                cnt_opn +=1
            else:
                pass
        else:
            pass                  
        if cnt_opn == 0 and len(l_opn) == 0:
            result += nb*nw
            #print(result)
            n=0
            nb=0
            nw=0
            #print("cls: "+str(l_cls))
            l_opn = []
            flag_next = True
        else:
            
            #print("opn: "+str(l_opn))
            flag_next = False
            pass
    result += nb*nw    
    print(result)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:56 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 20:43:41 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 18:42:51 2018

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')

def main():
    

if __name__ == '__main__':
    main()

"""

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

S = [input() for h in range(H)] 


def main():
    l_opn = []
    l_cls = list(range(H*W))
    l_masked=[]
    #print(l_cls)
    result = 0
    n=0
    h=0
    w=0
    nb=0
    nw=0
    flag_next = True
    while len(l_cls) != 0:
        cnt_opn = 0
        if flag_next:                
            l_opn.append(l_cls.pop(0))
            n = l_opn[0]
            h = n % H
            w = n // H
            if (S[h][w] == "#"):
                nb +=1
            else:
                nw +=1
            
        n = l_opn.pop(0)
        l_masked.append(n)
        h = n % H
        w = n // H
        
 
                
        if (w > 0) and ((n-H) in l_cls) and (S[h][w-1] != S[h][w]):
            l_opn.append(l_cls.pop(l_cls.index(n-H)))
            if (S[h][w-1] == "#"):
                nb +=1
            else:
                nw +=1
            cnt_opn +=1
        else:
            pass
            
        if (h > 0) and ((n-1) in l_cls) and (S[h-1][w] != S[h][w]):
            l_opn.append(l_cls.pop(l_cls.index(n-1)))
            if (S[h-1][w] == "#"):
                nb +=1
            else:
                nw +=1
            cnt_opn +=1         
        else:
            pass
        
        if (h < H-1) and ((n+1) in l_cls) and (S[h+1][w] != S[h][w]):
            l_opn.append(l_cls.pop(l_cls.index(n+1)))
            if (S[h+1][w] == "#"):
                nb +=1
            else:
                nw +=1
            cnt_opn +=1  
        else:
            pass    
                
        if (w < W-1) and ((n+H) in l_cls) and (S[h][w+1] != S[h][w]):
            l_opn.append(l_cls.pop(l_cls.index(n+H)))
            if (S[h][w+1] == "#"):
                nb +=1
            else:
                nw +=1
            cnt_opn +=1
        else:
            pass                  
        if cnt_opn == 0 and len(l_opn) == 0:
            result += nb*nw
            #print(result)
            n=0
            nb=0
            nw=0
            #print("cls: "+str(l_cls))
            l_opn = []
            flag_next = True
        else:
            
            #print("opn: "+str(l_opn))
            flag_next = False
            pass
    result += nb*nw    
    print(result)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 


ret=0
q = deque([]) 
def dfs(x,y,current):
	ret=0
	V=[ [ 0 for i in range(W) ] for j in range(H) ]
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.popleft()

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				next=S[x+dx][y+dy] 
				if V[x+dx][y+dy]==0 and current !=next:
						if next==".":  ret+=1
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy,next) )

	return ret




ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			q = deque([]) 
			ans+=dfs(x,y, "#")

print ans

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def solve(h, w, m, t):
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='#'):
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '#':
                            t[nci] = t[nci][:ncj]+'*'+t[nci][(ncj+1):]
                            if m[nci][ncj] == '#':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
            elif (m[i][j]=='#' and t[i][j]=='.'):
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '.':
                            t[nci] = t[nci][:ncj]+'*'+t[nci][(ncj+1):]
                            if m[nci][ncj] == '.':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
    return c

h, w = map(int,input().split())
m = ["*"*(w+2)]
for i in range(h):
    m.append("*"+input()+"*")
m.append("*"*(w+2))
mm = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==1:
            if m[i][j]=='#':
                mm[i] = mm[i][:j]+'.'+mm[i][(j+1):]
            else:
                mm[i] = mm[i][:j]+'#'+mm[i][(j+1):]
print(solve(h,w,m,mm))

Submission status: Time Limit Exceeded

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

combo = []

lis = [(0,-1),(-1,1),(1,1),(1,-1)]

def Adj(i, j):
    """
    隣接する頂点を取得
    """
    color = S[i][j]
    y = []
    for k in range(4):
        i += lis[k][0]
        j += lis[k][1]
        if not(i < 0 or i >= H or j < 0 or j >= W):
            if S[i][j] != color:
                y.append((i,j))
    return y

def search(i,j):
    """
    幅有線探索
    """
    start = (i,j)
    q = [[start]]
    y = []
    while len(q) > 0:
        add = False
        path = q.pop(0)
        adj = Adj(*path[-1])
        for x in adj:
            if x not in path:
                newpath = path[:]
                newpath.append(x)
                q.append(newpath)
                add = True
        if not add:
            y.append(path)
    tuples = []
    for tup in y:
        tuples = tuples + tup
    y = tuple(set(tuples))
    return y

def cellinpaths(paths, i, j):
    ret = True
    for path in paths:
        if (i,j)  in path:
            ret = False
            break
    return ret
        
paths = []

for i in range(H):
    for j in range(W):
        if cellinpaths(paths, i, j):
            if Adj(i, j):
                paths.append(search(i,j))

bw = []
for path in paths:
    b = 0
    w = 0
    for cell in path:
        if S[cell[0]][cell[1]] == "#":
            b += 1
        else:
            w += 1
    bw.append(b*w)

print(sum(bw))

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def solve(h, w, m, mm):
    t = mm
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    comp=0
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='#'):
                comp+=1
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '#':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '#':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
            elif (m[i][j]=='#' and t[i][j]=='.'):
                comp+=1
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '.':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '.':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
    return c

h, w = map(int,input().split())
m = [['*' for i in range(w+2)]]
for i in range(h):
    s = input()
    l = ['*']
    for j in range(w):
        l.append(s[j])
    l.append('*')
    m.append(l)
m.append(['*' for i in range(w+2)])
mm = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==1:
            if m[i][j]=='#':
                mm[i][j]='.'
            else:
                mm[i][j]='#'
print(solve(h,w,m,mm))

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def solve(h, w, m, mm):
    t = copy.deepcopy(mm)
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    comp=0
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='#'):
                comp+=1
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '#':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '#':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
            elif (m[i][j]=='#' and t[i][j]=='.'):
                comp+=1
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '.':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '.':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
    return c

h, w = map(int,input().split())
m = [['*' for i in range(w+2)]]
for i in range(h):
    s = input()
    l = ['*']
    for j in range(w):
        l.append(s[j])
    l.append('*')
    m.append(l)
m.append(['*' for i in range(w+2)])
mm = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==1:
            if m[i][j]=='#':
                mm[i][j]='.'
            else:
                mm[i][j]='#'
print(solve(h,w,m,mm))

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def solve_e(h, w, m, mm):
    t = copy.deepcopy(mm)
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    comp=0
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='#'):
                comp+=1
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '#':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '#':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
    return c

def solve_o(h, w, m, mm):
    t = copy.deepcopy(mm)
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    comp=0
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='.'):
                comp+=1
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '.':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '.':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
    return c

h, w = map(int,input().split())
m = [['*' for i in range(w+2)]]
for i in range(h):
    s = input()
    l = ['*']
    for j in range(w):
        l.append(s[j])
    l.append('*')
    m.append(l)
m.append(['*' for i in range(w+2)])
mm = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==1:
            if m[i][j]=='#':
                mm[i][j]='.'
            else:
                mm[i][j]='#'
print(solve_e(h,w,m,mm)+solve_o(h,w,m,mm))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]
b, w = 0, 0

def dfs(i, j):
    global b, w

    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W:
            if S[i][j] != S[ni][nj] and not visited[ni][nj]:
                dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def solve(h, w, m, mm):
    t = copy.deepcopy(mm)
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    comp=0
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='#'):
                comp+=1
                bl, wh = 0, 0
                q = queue.Queue()
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '#':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '#':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
    return c

h, w = map(int,input().split())
m = [['*' for i in range(w+2)]]
for i in range(h):
    s = input()
    l = ['*']
    for j in range(w):
        l.append(s[j])
    l.append('*')
    m.append(l)
m.append(['*' for i in range(w+2)])
e = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==0:
            if m[i][j]=='.':
                e[i][j]='*'
        else:
            if m[i][j]=='#':
                e[i][j]='*'
            else:
                e[i][j]='#'
o = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==1:
            if m[i][j]=='.':
                o[i][j]='*'
        else:
            if m[i][j]=='#':
                o[i][j]='*'
            else:
                o[i][j]='#'
print(solve(h,w,m,e)+solve(h,w,m,o))

Submission status: Time Limit Exceeded

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [[0]]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          for k in LT[M[i][j-1]]:
            LT[k].extend(LT[M[i-1][j]])
            LT[k] = list(set(LT[k]))
          for k in LT[M[i-1][j]]:
            LT[k].extend(LT[M[i][j-1]])
            LT[k] = list(set(LT[k]))
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append([len(LT)])
        
LT = get_unique_list(LT)
L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
    for k in range(len(LT)):
      if M[i][j] in LT[k]:
        L[k].append((i, j))
        break

cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)