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: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append([i,j])
        while q:
          y,x=q.popleft()
          if visited[y][x]:
            continue
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx
            if 0<=ny<h and 0<=nx<w:
              if field[y][x]==field[ny][nx]:
                continue
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='.':
                # ans+=1
                pass
              q.append([ny,nx])
    # print(ans)
  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          if visited[y][x]:
            continue
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx
            if 0<=ny<h and 0<=nx<w:
              if field[y][x]==field[ny][nx]:
                continue
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='.':
                # ans+=1
                pass
              q.append((ny,nx))
    print(ans)
  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [input() for _ in range(h)]

ans = 0
already = [[False]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if grid[i][j] == "." or already[i][j]:
      continue
    already[i][j] = True
    not_yet = deque([(i, j)])
    black, white = 0, 0
    countlist = dict()
    countlist[(i, j)] = 0
    while not_yet:
      p, q = not_yet.popleft()
      judge = True if grid[p][q] == "#" else False
      if not judge:
        white += 1
      count = 0
      if p > 0 and not already[p-1][q] and grid[p-1][q] != grid[p][q]:
        if not (p-1, q) in countlist:
          not_yet.append((p-1, q))
          countlist[p-1, q] = 0
          count += 1
      if p < h-1 and not already[p+1][q] and grid[p+1][q] != grid[p][q]:
        if not (p+1, q) in countlist:
          not_yet.append((p+1, q))
          countlist[(p+1, q)] = 0
          count += 1
      if q > 0 and not already[p][q-1] and grid[p][q-1] != grid[p][q]:
        if not (p, q-1) in countlist:
          not_yet.append((p, q-1))
          countlist[p, q-1] = 0
          count += 1
      if q < w-1 and not already[p][q+1] and grid[p][q+1] != grid[p][q]:
        if not (p, q+1) in countlist:
          not_yet.append((p, q+1))
          countlist[p, q+1] = 0
          count += 1
      if judge and count:
        already[p][q] = True
        black += 1
    ans += black*white

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import *
h,W=map(int,input().split())
s=[]
b=[]
w=[]
ans=0
l=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    ss=list(input())
    for j in range(W):
        if ss[j]=="#":
            b.append((i,j))
        else:
            w.append((i,j))
for x,y in b:
    for x2,y2 in w:
        flg=[[False for k in range(W)] for m in range(h)  ]
        que=deque()
        que.append((x,y,0))
        while que:
            i,j,bw=que.popleft()
            flg[i][j]=True
            if i==x2 and j==y2:
                ans+=1
                break
            for xx,yy in l:
                nx,ny=x+xx,y+yy
                if 0<=nx<h and 0<=ny<W:
                    if flg[nx][ny]==False:
                        if bw==0 and (nx,ny) in w:
                            que.append((nx,ny,1))
                        if bw==1 and (nx,ny) in b:
                            que.append((nx,ny,0))

print(ans)

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

H, W = read_values()
P = [[False for _ in range(W)] for _ in range(H)]
F = [input().strip() for i in range(H)]

def f(h, w):
    S = deque()
    S.append((h, w))
    P[h][w] = True
    T = [0, 1]
    while S:
        h, w = S.popleft()
        for hh, ww in [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]:
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if P[hh][ww]:
                continue
            if F[hh][ww] == F[h][w]:
                continue
            P[hh][ww] = True
            t = 1 if F[hh][ww] == "." else 0
            T[t] += 1
            S.append((hh, ww))
    return T[0] * T[1]


def main():
    res = 0
    for h in range(H):
        for w in range(W):
            if P[h][w] or F[h][w] != "#":
                continue
            res += f(h, w)
    print(res)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

H, W = map(int,input().split())
S = [input() for _ in range(H)]
#%%
visited = [[False]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def dfs(x,y,res, numW,numK,state):
    # print(x,y,res)
    # state=0: next=Black
    # state=1: next=White
    newres = 0
    flag = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue
        if visited[nx][ny]:
            continue
        if state==0 and S[nx][ny]=='#':
            visited[nx][ny] = True
            newres += dfs(nx,ny,res+numW,numW,numK+1,1)
            flag = False
        elif state==1 and S[nx][ny]=='.':
            visited[nx][ny] = True
            newres += dfs(nx,ny,res+numK,numW+1,numK,0)
            flag = False
    
    # if flag:
    #     visited[x][y] = False
    if S[x][y]=='.':
        return newres + numK
    elif S[x][y]=='#':
        return newres + numW

ans = 0
for i in range(H):
    for j in range(W):
        if not visited[i][j]:
            numW = S[i][j]=='.'
            numK = S[i][j]=='#'
            visited[i][j] = True
            ans += dfs(i,j,0,numW,numK,numK)
            # print('X,Y =',i,j,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

h, w = map(int, input().split())
S = []
for i in range(h):
    s = input()
    S.append(s)

uf = UnionFind(h*w)

for i in range(h):
    for j in range(w):
        if i < h - 1 and S[i][j] != S[i+1][j]:
            uf.union(i*w+j, (i+1)*w+j)
        if j < w - 1 and S[i][j] != S[i][j+1]:
            uf.union(i*w+j, i*w+j+1)

ans = 0

d = defaultdict(int)

for i, x in enumerate(uf.parents):
    if x < 0:
        if S[i//w][i%w] == '.':
            d[i] += 1
    else:
        if S[i//w][i%w] == '.':
            d[x] += 1

for i, x in enumerate(uf.parents):
    if x < 0:
        # print(-x, d[i])
        cnt = -x
        ans += d[uf.find(i)] * (cnt-d[i])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

h, w = map(int, input().split())
S = []
for i in range(h):
    s = input()
    S.append(s)

uf = UnionFind(h*w)

for i in range(h):
    for j in range(w):
        if i < h - 1 and S[i][j] != S[i+1][j]:
            uf.union(i*w+j, (i+1)*w+j)
        if j < w - 1 and S[i][j] != S[i][j+1]:
            uf.union(i*w+j, i*w+j+1)

ans = 0

d = defaultdict(int)

for i, x in enumerate(uf.parents):
    if x < 0:
        if S[i//w][i%w] == '.':
            d[i] += 1
    else:
        if S[i//w][i%w] == '.':
            d[x] += 1

for i, x in enumerate(uf.parents):
    if x < 0:
        cnt = -x
        ans += d[i] * (cnt-d[i])

print(ans)

Submission status: Wrong Answer

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==(".","#") :
                unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
ans = 0
####
for i in range(h+2):
    for j in range(w+2):
        root((i,j))
pb = {}
pw = {}
for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="#":
            if k in pb:
                pb[k]+=1
            else:
                pb[k]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[k]+=1
            else:
                pw[k]=1
ans = 0
c2 =  set([p[i][j] for j in range(w+2) for i in range(h+2)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Submission status: Wrong Answer

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==(".","#") :####
                unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
ans = 0
####これ
for i in range(h+2):
    for j in range(w+2):
        root((i,j))
pb = {}
pw = {}
for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="#":
            if k in pb:
                pb[k]+=1
            else:
                pb[k]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[k]+=1
            else:
                pw[k]=1
ans = 0
c2 =  set([p[i][j] for j in range(1,w+1) for i in range(1,h+1)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Submission status: Wrong Answer

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(h+2):
    for j in range(w+2):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if 0<=i2<h+2 and 0<=j2<w+2:
                if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==("#",".") :
                    unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
ans = 0
####これ
for i in range(h+2):
    for j in range(w+2):
        root((i,j))
pb = {}
pw = {}
for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="#":
            if k in pb:
                pb[k]+=1
            else:
                pb[k]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[k]+=1
            else:
                pw[k]=1
ans = 0
c2 =  set([p[i][j] for j in range(1,w+1) for i in range(1,h+1)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Submission status: Wrong Answer

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(h+2):
    for j in range(w+2):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if 0<=i2<h+2 and 0<=j2<w+2:
                if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==("#",".") :
                    unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(w+2)] for i in range(h+2)]
ans = 0

pb = {}
pw = {}
for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="#":
            if k in pb:
                pb[k]+=1
            else:
                pb[k]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[k]+=1
            else:
                pw[k]=1
ans = 0
c2 =  set([p[i][j] for j in range(w+2) for i in range(h+2)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Submission status: Wrong Answer

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(h+2):
    for j in range(w+2):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if 0<=i2<h+2 and 0<=j2<w+2:
                if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==("#",".") :
                    unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
ans = 0

pb = {}
pw = {}
for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="#":
            if k in pb:
                pb[k]+=1
            else:
                pb[k]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[k]+=1
            else:
                pw[k]=1
ans = 0
c2 =  set([p[i][j] for j in range(1,w+1) for i in range(1,h+1)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w = map(int, input().split())
n = h*w
fld = ''.join([input()for _ in range(h)])
edges = [[]for _ in range(n)]


def to_v(i, j):
    return i*w+j


for i in range(h):
    for j in range(w):
        v = to_v(i, j)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            x, y = i+di, j+dj
            if x < 0 or h <= x or y < 0 or w <= y:
                continue
            v2 = to_v(x, y)
            if fld[v] != fld[v2]:
                edges[v].append(v2)
                edges[v2].append(v)


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in edges[v]:
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [['.']*(W+2)] + [['.'] + list(input()) + ['.'] for _ in range(H)] + [['.']*(W+2)]
for i in range(1, H+1):
  S[i][0] = S[i][1]
  S[i][-1] = S[i][-2]
for i in range(1, W+1):
  S[0][i] = S[1][i]
  S[-1][i] = S[-2][i]
S[0][0] = S[0][1]
S[-1][0] = S[-2][0]
S[0][-1] = S[0][-2]
S[-1][-1] = S[-2][-1]
V = [[0 for _ in range(W+2)] for i in range(H+2)]
num = 0
for i in range(1, H+1):
  for j in range(1, W+1):
    if S[i][j] == '#' and V[i][j] == 0:
      V[i][j] = 1
      p = [[i, j]]
      cnt = 1
      pnt = 0
      D = {'.': 0, '#': 0}
      D[S[i][j]] = 1
      while pnt < cnt:
        n = cnt
        for k in range(pnt, cnt):
          x = p[pnt][:]
          y = S[x[0]][x[1]][:]
          if S[x[0]-1][x[1]] != y and V[x[0]-1][x[1]] == 0:
            V[x[0]-1][x[1]] = 1
            p.append([x[0]-1, x[1]])
            D[S[x[0]-1][x[1]]] += 1
            cnt += 1
          if S[x[0]+1][x[1]] != y and V[x[0]+1][x[1]] == 0:
            V[x[0]+1][x[1]] = 1
            p.append([x[0]+1, x[1]])
            D[S[x[0]+1][x[1]]] += 1
            cnt += 1
          if S[x[0]][x[1]-1] != y and V[x[0]][x[1]-1] == 0:
            V[x[0]][x[1]-1] = 1
            p.append([x[0], x[1]-1])
            D[S[x[0]][x[1]-1]] += 1
            cnt += 1
          if S[x[0]][x[1]+1] != y and V[x[0]][x[1]+1] == 0:
            V[x[0]][x[1]+1] = 1
            p.append([x[0], x[1]+1])
            D[S[x[0]][x[1]+1]] += 1
            cnt += 1
        pnt = n
      num += D['.'] * D['#']
print(num)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(S,H,W,sh,sw):
    black,white=0,0
    d=deque()
    d.append([sh,sw])
    if S[sh][sw]=='#':
        black+=1
    elif S[sh][sw]=='.':
        white+=1
    seen[sh][sw]=1
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(seen[nh][nw] or S[nh][nw]==S[h][w]):
                continue
            if S[nh][nw]=='#':
                black+=1
            else:
                white+=1
            seen[nh][nw]=1
            d.append([nh,nw])
    return white,black

Submission status: Wrong Answer

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

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

visited = set()
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(node, white, count):
  global visited
  x, y = node
  count += 1
  for i, (dx, dy) in enumerate(dxy):
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and S[xx][yy]=='.':
      white.add((xx, yy))
      for ddx, ddy in [dxy[(i-1)%4], dxy[(i+1)%4]]:
        xxx = xx + ddx; yyy = yy + ddy
        if 0<=xxx<H and 0<=yyy<W and S[xxx][yyy]=='#' and (xxx, yyy) not in visited:
          visited.add((xxx, yyy))
          white, count = dfs((xxx, yyy), white, count)
  return white, count

for x in range(H):
  for y in range(W):
    if S[x][y] == '#' and (x, y) not in visited:
      visited.add((x, y))
      white, count = dfs((x, y), set(), 0)
      ans += len(white) * count

print(ans)

Submission status: Wrong Answer

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

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

visited = set()
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(node, white, count):
  global visited
  x, y = node
  count += 1
  for i, (dx, dy) in enumerate(dxy):
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W:
      if S[xx][yy]=='.':
        white.add((xx, yy))
      ddx, ddy = dxy[(i+1)%4]
      xxx = xx + ddx; yyy = yy + ddy
      if 0<=xxx<H and 0<=yyy<W and S[xxx][yyy]=='#' and (xxx, yyy) not in visited:
        visited.add((xxx, yyy))
        white, count = dfs((xxx, yyy), white, count)
  return white, count

for x in range(H):
  for y in range(W):
    if S[x][y] == '#' and (x, y) not in visited:
      visited.add((x, y))
      white, count = dfs((x, y), set(), 0)
      ans += len(white) * count

print(ans)

Submission status: Wrong Answer

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

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

visited = set()
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(node, white, count):
  global visited
  x, y = node
  count += 1
  for i, (dx, dy) in enumerate(dxy):
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and S[xx][yy]=='.':
      white.add((xx, yy))
      ddx, ddy = dxy[(i+1)%4]
      xxx = xx + ddx; yyy = yy + ddy
      if 0<=xxx<H and 0<=yyy<W and S[xxx][yyy]=='#' and (xxx, yyy) not in visited:
        visited.add((xxx, yyy))
        white, count = dfs((xxx, yyy), white, count)
  return white, count

for x in range(H):
  for y in range(W):
    if S[x][y] == '#' and (x, y) not in visited:
      visited.add((x, y))
      white, count = dfs((x, y), set(), 0)
      ans += len(white) * count

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [input() for i in range(H)]
dp = [[0]*W for i in range(H)]
ans = 0
dij = [[0, -1], [-1, 0]]
for i in range(H):
  for j in range(W):
    c = S[i][j]
    flag = False
    for di, dj in dij:
      ii = i + di; jj = j + dj
      if 0<=ii<H and 0<=jj<W and S[ii][jj]!=c:
        flag = True
        dp[i][j] += 1
    if flag:
      ii = i - 1; jj = j - 1
      if 0<=ii<H and 0<=jj<W and S[ii][jj] == c:
        dp[i][j] += dp[ii][jj]
    ans += dp[i][j]

print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

H, W = getNM()
maze = []
for i in range(H):
    m = list(input())
    maze.append(m)

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

memo = [[-1] * W for i in range(H)]

def counter(sx, sy):
    black_cnt = 0
    white_cnt = 0

    memo[sy][sx] = 1
    if maze[sy][sx] == "#":
        black_cnt += 1
    else:
        white_cnt += 1

    pos = deque([[sx, sy]])

    while len(pos) > 0:
        x, y = pos.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != maze[y][x] and memo[ny][nx] == -1:
                memo[ny][nx] = 1
                pos.append([nx, ny])
                if maze[ny][nx] == "#":
                    black_cnt += 1
                else:
                    white_cnt += 1
    return black_cnt * white_cnt

ans = 0
for i in range(H):
    for j in range(W):
        ans += counter(j, i)
print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

H, W = getNM()
maze = []
for i in range(H):
    m = list(input())
    maze.append(m)

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

memo = [[-1] * W for i in range(H)]

def counter(sx, sy):
    black_cnt = 0
    white_cnt = 0

    memo[sy][sx] = 1
    if maze[sy][sx] == "#":
        black_cnt += 1
    else:
        white_cnt += 1

    pos = deque([[sx, sy]])

    while len(pos) > 0:
        x, y = pos.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != maze[y][x] and memo[ny][nx] == -1:
                memo[ny][nx] = 1
                pos.append([nx, ny])
                if maze[ny][nx] == "#":
                    black_cnt += 1
                else:
                    white_cnt += 1
    return black_cnt * white_cnt

ans = 0
for i in range(H):
    for j in range(W):
        ans += counter(j, i)
print(ans)