Problem:


Surrounding Area

土地囲い

English text is not available in this practice contest.

ある 2 人の不動産屋が，客船に乗って南の島に向かっていた．青い空，さわやかな風…．2 人は他の乗客とともに船旅を楽しんでいた．ところが，ある日突然発生した竜巻によって客船が沈んでしまった．他の乗客は救助隊によって救助されたが，どういうわけかこの 2 人だけ見落とされてしまった．数日の漂流の後，彼らはある無人島に流れ着いた．この無人島は長方形であり，以下の図のように格子に区切られていた．

図 C-1: 無人島の形状

彼らはとても欲深かったので，助けを呼ぶことではなく，この無人島の土地を売ることを考えていた．そして，彼らは土地を折半するということはせず，土地の奪い合いを始めた．彼らはそれぞれ自分の土地にしたいところを，一方は黒い杭で，もう一方は白い杭で囲み始めた．全ての杭は格子の中央に打たれ，また 1 つの格子に複数の杭が打たれることはなかった．しばらくすると双方とも疲れ果てて，杭を打つことを止めた．

あなたの仕事は，黒い杭および白い杭で囲まれた土地の面積を求めるプログラムを書くことである．ただし，格子 (i, j) が黒い杭に囲まれているとは，直感的には「格子 (i, j) から上下左右に任意に移動したとき，最初に当たる杭は常に黒い杭である」ことを意味する．正確には以下のように定義される．

黒い杭に「拡大隣接した」格子を次のとおりに定める．白い杭についても同様とする．

格子 (i, j) に杭が存在せず，さらに格子 (i, j) に隣接する格子のいずれかに黒い杭が存在するならば，格子 (i, j) は黒い杭に拡大隣接している．

格子 (i, j) に杭が存在せず，さらに格子 (i, j) に隣接する格子のいずれかが黒い杭に拡大隣接しているならば，格子 (i, j) は黒い杭に拡大隣接している．このルールは再帰的に適用される．

このとき，格子 (i, j) が黒い杭に拡大隣接していて，さらに白い杭に隣接していないとき，またそのときに限って，格子 (i, j) が黒い杭に囲まれているという．また逆に，格子 (i, j) が白い杭に拡大隣接していて，さらに黒い杭に隣接していないとき，またそのときに限って，格子 (i, j) が白い杭に囲まれているという．

Input

入力は複数のデータセットから構成される．各データセットは以下のような構成になっている．

w h

a1,1 a2,1 a3,1 ... aw,1

a1,2 a2,2 a3,2 ... aw,2

...

a1,h a2,h a3,h ... aw,h

w は土地の横幅，h は土地の縦幅を表す．これらは 1 ≦ w,h ≦ 50 を満たす．各 ai,j は格子 (i, j) の状態を表す 1 つの半角文字であり，「B」は黒い杭が打たれていることを，「W」は白い杭が打たれていることを，「.」（ピリオド）はいずれの杭も打たれていないことをそれぞれ示す．

w = h = 0 は入力の終端を表しており，データセットには含まれない．

Output

各データセットについて，黒い杭が囲んだ土地の大きさ，および白い杭が囲んだ土地の大きさを 1 つの空白で区切って 1 行に出力しなさい．

Sample Input

10 10
.....W....
....W.W...
...W...W..
....W...W.
.....W...W
......W.W.
BBB....W..
..B..BBBBB
..B..B....
..B..B..W.
5 3
...B.
...BB
.....
1 1
.
0 0

Output for the Sample Input

6 21
12 0
0 0



Sample input:
10 10
.....W....
....W.W...
...W...W..
....W...W.
.....W...W
......W.W.
BBB....W..
..B..BBBBB
..B..B....
..B..B..W.
5 3
...B.
...BB
.....
1 1
.
0 0


Sample output:
6 21
12 0
0 0

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(3000)
def dfs(r, c, n):
    board[r][c] = n
    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if 0 <= nr < h and 0 <= nc < w and board[nr][nc] != n:
            if board[nr][nc] in 'WB':
                pile.append(board[nr][nc])
                continue
            dfs(nr, nc, n)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    board = [list(input()) for _ in range(h)]
    place = 0
    piles = []
    black, white = [], []
    for r in range(h):
        for c in range(w):
            if board[r][c] == '.':
                pile = []
                place += 1
                dfs(r, c, place)
                piles.append(pile)
    for i, pile in enumerate(piles):
        if not pile: continue
        if all(p == 'B' for p in pile):
            black.append(i)
        elif all(p == 'W' for p in pile):
            white.append(i)

    ans_b, ans_w = 0, 0
    for row in board:
        for c in row:
            if c in black:
                ans_b += 1
            elif c in white:
                ans_w += 1
    print(ans_b, ans_w)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
while True:
  w,h=map(int,input().split())
  if w==0:
    break
  mp=["X"+input()+"X" for _ in range(h)]
  mp.insert(0,"X"*(w+2))
  mp.append('X'*(w+2))

  visited_w=[[False]*(w+2) for _ in range(h+2)]
  visited_b=[[False]*(w+2) for _ in range(h+2)]
  vec=((0,1),(0,-1),(1,0),(-1,0))

  def search(x,y,visited):
    for dx, dy in vec:
      nx,ny=x+dx,y+dy
      if not visited[ny][nx] and mp[ny][nx]==".":
        visited[ny][nx]=True
        search(nx,ny,visited)

  for y in range(1,h+1):
    for x in range(1,w+1):
      if mp[y][x]=="W":
        search(x,y,visited_w)
      elif mp[y][x]=="B":
        search(x,y,visited_b)

  ans_w=ans_b=0

  for y in range(1,h+1):
    for x in range(1,w+1):
      if visited_w[y][x] and not visited_b[y][x]:
        ans_w +=1
      elif not visited_w[y][x] and visited_b[y][x]:
        ans_b+=1
  print(ans_b,ans_w)

Submission status: Accepted

Solution code:
import sys
def ds4(here, lb, ub, field, label):
	if not field[here[1]][here[0]][label]:
		field[here[1]][here[0]][label] = True
	
		if lb[0] < here[0]:
			ds4((here[0]-1, here[1]), lb, ub, field, label)

		if lb[1] < here[1]:
			ds4((here[0], here[1]-1), lb, ub, field, label)
			
		if ub[0] > here[0]:
			ds4((here[0]+1, here[1]), lb, ub, field, label)
			
		if ub[1] > here[1]:
			ds4((here[0], here[1]+1), lb, ub, field, label)

sys.setrecursionlimit(10000)	
while 1:
	w,h = map(int,raw_input().split())
	if (w,h) == (0,0):
		break
	W = []
	B = []
	island = [[[False, False] for i in range(w)] for j in range(h)]
	for j in range(h):
		s = raw_input()
		for i in range(w):
			if s[i] == "B":
				island[j][i][0] = True
				B.append((i,j))
			elif s[i] == "W":
				island[j][i][1] = True
				W.append((i,j))
	for wh in W:
		ds4(wh,(0,0),(w-1,h-1),island,0)
	for bl in B:
		ds4(bl,(0,0),(w-1,h-1),island,1)
	wnum = bnum = 0
	for j in range(h):
		for i in range(w):
			if island[j][i][0]^island[j][i][1]:	
				if island[j][i][0] and not island[j][i][1]:
					wnum += 1
				elif island[j][i][1] and not island[j][i][0]:
					bnum += 1
	print bnum, wnum

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000)
def rec(x,y,c):
    if   A[y][x] == ".": A[y][x] = c
    elif A[y][x] != c  : A[y][x] = "x"
    for dx,dy in zip([1,0,-1,0],[0,1,0,-1]):
        nx,ny = x+dx,y+dy
        if 0 <= nx < w and 0 <= ny < h and A[ny][nx] in [".","b" if c == "w" else "w"]:
            rec(nx,ny,c)

while 1:
    w,h = map(int,raw_input().split())
    if w == 0: break
    A = [list(raw_input()) for _ in range(h)]
    for y in range(h):
        for x in range(w):
            if A[y][x] == "W": rec(x,y,"w")
            if A[y][x] == "B": rec(x,y,"b")
    print sum(Ai.count("b") for Ai in A),sum(Ai.count("w") for Ai in A)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            w, h = map(int, raw_input().split())
            if w == h == 0:
                break
            m = []
            for i in range(1, h+1):
                row = list(raw_input())
                m.append(row)
            # for row in m:
            #     print row
            # print 
            d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            w_count = 0
            b_count = 0
            for i in range(h):
                for j in range(w):
                    if m[i][j] == '.':
                        q = [(i, j)]
                        flg = None
                        count = 0
                        while q:
                            y, x = q.pop()
                            if m[y][x] == '.':
                                count += 1
                            m[y][x] = 'U'
                            for dy, dx in d:
                                if 0 <= y + dy < h and 0 <= x + dx < w:
                                    if m[y+dy][x+dx] == 'W':
                                        if flg is None:
                                            flg = 'W'
                                        elif flg == 'B':
                                            flg = 'NotOccupied'
                                    elif m[y+dy][x+dx] == 'B':
                                        if flg is None:
                                            flg = 'B'
                                        elif flg == 'W':
                                            flg = 'NotOccupied'
                                    elif m[y+dy][x+dx] == '.':
                                        q.append((y + dy, x + dx))
                                                                            
                        if flg == 'W':
                            w_count += count
                        elif flg == 'B':
                            b_count += count
                        # for row in m:
                        #     print row
                        # print b_count, w_count
                        # print 
                            
            print b_count, w_count
                                                
                                    
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-

def dfs(Map, used, i, j):
    cnt = 0
    wc = False
    bc = False
    q = [[i, j]]
    used[i][j] = True
    while q!=[]:
        cnt += 1
        i = q[0][0]
        j = q[0][1]
        if Map[i][j] == 'W':
            wc = True
        elif Map[i][j] == 'B':
            bc = True
        q.pop(0)
        if i-1>=0:
            if Map[i-1][j] == 'W':
                wc = True
            elif Map[i-1][j] == 'B':
                bc = True
            elif used[i-1][j] == False:
                q.append([i-1, j])
                used[i-1][j] = True
        if i+1<len(used):
            if Map[i+1][j] == 'W':
                wc = True
            elif Map[i+1][j] == 'B':
                bc = True
            elif used[i+1][j] == False:
                q.append([i+1, j])
                used[i+1][j] = True
        if j-1>=0:
            if Map[i][j-1] == 'W':
                wc = True
            elif Map[i][j-1] == 'B':
                bc = True
            elif used[i][j-1] == False:
                q.append([i, j-1])
                used[i][j-1] = True
        if j+1<len(used[i]):
            if Map[i][j+1] == 'W':
                wc = True
            elif Map[i][j+1] == 'B':
                bc = True
            elif used[i][j+1] == False:
                q.append([i, j+1])
                used[i][j+1] = True
    if wc == True and bc == True:
        return int(0)
    elif wc == True:
        return -int(cnt)
    elif bc == True:
        return int(cnt)
    else:
        return 0

while 1:
    (w, h) = map(int, raw_input().split())
    if w==0: break
    M = []
    [wr, br] = [0, 0]
    for i in range(h):
        M.append(raw_input())
    used = [[False]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if M[i][j] in ('W','B'): used[i][j] = True
    for i in range(h):
        for j in range(w):
            if used[i][j] == False:
                s = dfs(M, used, i, j)
                if s < 0:
                    wr -= s
                elif s > 0:
                    br += s
    print br, wr

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y, symbol,land):
    if land[y][x] != '.':
        return ([land[y][x]] if not str(land[y][x]).isnumeric() else False), 0
    land[y][x] = symbol
    count = 1
    dxdy = [(1,0),(-1,0),(0,1),(0,-1)]

    owner_list = []
    for dx,dy in dxdy:
        if 0 <= x + dx < len(land[0]) and 0 <= y + dy < len(land):
            ret,c = dfs(x + dx, y + dy, symbol,land)
            count += c

            if ret is not False:
                owner_list += ret
    return (list(set(owner_list)), count)

while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    land = [list(input()) for i in range(0,h)]

    symbol = 0
    count_dict = {'W' :0, 'B' :0}

    for y in range(h):
        for x in range(w):
            if land[y][x] == '.':
                ret, count = dfs(x,y,symbol,land)
                if len(ret) == 1:
                    count_dict[ret[0]] += count
                symbol += 1
    print(count_dict['B'],count_dict['W'])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000)
def dfs(r, c, n):
    board[r][c] = n
    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if 0 <= nr < h and 0 <= nc < w and board[nr][nc] != n:
            if board[nr][nc] in 'WB':
                pile.append(board[nr][nc])
                continue
            dfs(nr, nc, n)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    board = [list(input()) for _ in range(h)]
    place = 0
    piles = []
    black, white = [], []
    for r in range(h):
        for c in range(w):
            if board[r][c] == '.':
                pile = []
                place += 1
                dfs(r, c, place)
                piles.append(pile)
    for i, pile in enumerate(piles):
        if not pile: continue
        for p in pile:
            if p != 'B':
                break
        else:
            black.append(i+1)
        for p in pile:
            if p != 'W':
                break
        else:
            white.append(i+1)
    ans_b, ans_w = 0, 0
    for row in board:
        for c in row:
            if c in black:
                ans_b += 1
            elif c in white:
                ans_w += 1
    print(ans_b, ans_w)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000)
def dfs(r, c, n):
    board[r][c] = n
    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if 0 <= nr < h and 0 <= nc < w and board[nr][nc] != n:
            if board[nr][nc] in 'WB':
                pile.append(board[nr][nc])
                continue
            dfs(nr, nc, n)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    board = [list(input()) for _ in range(h)]
    place = 0
    piles = []
    black, white = [], []
    for r in range(h):
        for c in range(w):
            if board[r][c] == '.':
                pile = []
                place += 1
                dfs(r, c, place)
                piles.append(pile)

    for i, pile in enumerate(piles):
        if not pile: continue
        if all(p == 'B' for p in pile):
            black.append(i+1)
        elif all(p == 'W' for p in pile):
            white.append(i+1)

    ans_b, ans_w = 0, 0
    for row in board:
        for c in row:
            if c in black:
                ans_b += 1
            elif c in white:
                ans_w += 1
    print(ans_b, ans_w)

Submission status: Accepted

Solution code:
class Area:
    def __init__(self,m,x,y):
        self.m = m
        self.f_W = False
        self.f_B = False
        self.side = 0
        self.count = 0
        self.standardx = x
        self.standardy = y
        self.check(x,y)
        self.getSide()

    def check(self,x,y):
        if(y<0 or y >= len(m) or x<0 or x>=len(m[0])):
            return
        c = self.m[y][x]
        if(c!=0):
            if(c==1):
                self.f_B=True
            if(c==2):
                self.f_W=True
            return
        else:
            if(c==0):
                self.m[y][x]=3
                self.count += 1
                self.check(x-1,y)
                self.check(x+1,y)
                self.check(x,y-1)
                self.check(x,y+1)

    def getSide(self):
        if(self.f_B and self.f_W):
            self.side = 0
        elif(self.f_B):
            self.side = 1
        elif(self.f_W):
            self.side = 2
        else:
            self.side = 0
        return self.side
            
import sys
limit = 100000
sys.setrecursionlimit(limit)


while True:
    w,h = map(int,raw_input().split())
    if(not w) :
        break
    m = []
    for i in range(h):
        m.append([])
        l = raw_input()
        for ii in range(w):
            dic = {".":0,"B":1,"W":2}
            m[i].append(dic[l[ii]])
    B = 0
    W = 0
    for i,l in enumerate(m):
        for ii,c in enumerate(l):
            if(c==0):
                a = Area(m,ii,i)
                if(a.getSide() == 1):
                    B += a.count
                elif(a.getSide() == 2):
                    W += a.count
    print B,W

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(2502)


def paint(field, i, j, b, f, moves={(-1, 0), (1, 0), (0, 1), (0, -1)}):
    fij = field[i][j]
    if fij & f:
        return
    if fij & 4 and not fij & b:
        return
    field[i][j] |= b | f
    for di, dj in moves:
        ni = i + di
        nj = j + dj
        if nj < 0 or w <= nj or ni < 0 or h <= ni:
            continue
        paint(field, ni, nj, b, f)


buf = []
chardict = {'.': 0, 'W': 5, 'B': 6}
while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    field = []
    init_w, init_b = 0, 0
    for _ in range(h):
        line = input().strip()
        init_w += line.count('W')
        init_b += line.count('B')
        field.append([chardict[c] for c in line])
    for i in range(h):
        for j in range(w):
            fij = field[i][j]
            if fij & 4 and not fij & 24:
                paint(field, i, j, fij & 3, (fij & 3) << 3)
    result = Counter(b & 3 for row in field for b in row)
    print(result[2] - init_b, result[1] - init_w)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(2502)


def paint(field, i, j, b, f, moves={(-1, 0), (1, 0), (0, 1), (0, -1)}):
    fij = field[i][j]
    if fij & f:
        return
    if fij & 4 and not fij & b:
        return
    field[i][j] |= b | f
    for di, dj in moves:
        ni = i + di
        nj = j + dj
        if nj < 0 or w <= nj or ni < 0 or h <= ni:
            continue
        paint(field, ni, nj, b, f)


buf = []
chardict = {'.': 0, 'W': 5, 'B': 6}
while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    field = [[chardict[c] for c in input()] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            fij = field[i][j]
            if fij & 4 and not fij & 24:
                paint(field, i, j, fij & 3, (fij & 3) << 3)
    result = Counter(b & 7 for row in field for b in row)
    print(result[2], result[1])

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(2502)


def paint(field, i, j, b, f, moves={(-1, 0), (1, 0), (0, 1), (0, -1)}):
    fij = field[i][j]
    if fij & f:
        return
    if fij & 4 and not fij & b:
        return
    field[i][j] |= b | f
    for di, dj in moves:
        ni = i + di
        nj = j + dj
        if nj < 0 or w <= nj or ni < 0 or h <= ni:
            continue
        paint(field, ni, nj, b, f)


buf = []
chardict = {'.': 0, 'W': 5, 'B': 6}
while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    field = [[chardict[c] for c in input()] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            fij = field[i][j]
            if fij & 4 and not fij & 24:
                paint(field, i, j, fij & 3, (fij & 3) << 3)
    result = Counter(b & 7 for row in field for b in row)
    buf.append('{} {}'.format(result[2], result[1]))
print('\n'.join(buf))

Submission status: Accepted

Solution code:
from collections import deque

dxs = [1,0,-1,0]
dys = [0,1,0,-1]
def bfs(x,y,c):
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        for dx,dy in zip(dxs,dys):
            nx,ny = x+dx,y+dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H: continue
            if src[ny][nx] != '.' or mem[c][ny][nx]: continue
            q.append((nx,ny))
            mem[c][ny][nx] = 1

while True:
    W,H = map(int,input().split())
    if W == 0: break
    src = [input() for i in range(H)]
    mem = [[[0 for w in range(W)] for h in range(H)] for c in range(2)]
    for y in range(H):
        for x in range(W):
            if src[y][x] == '.': continue
            c = (0 if src[y][x] == 'B' else 1)
            bfs(x,y,c)
    b = w = 0
    for y in range(H):
        for x in range(W):
            bm,wm = mem[0][y][x], mem[1][y][x]
            if bm and not wm: b += 1
            elif wm and not bm: w += 1
    print(str(b) + ' ' + str(w))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

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

    while True:
        w,h = LI()
        if w == 0 and h == 0:
            break

        a = [S() for _ in range(h)]
        b = [[0]*w for _ in range(h)]
        c = [[0]*w for _ in range(h)]
        q = []
        for i in range(h):
            for j in range(w):
                if a[i][j] == 'B':
                    q.append((i,j))
        qi = 0
        f = [[None]*w for _ in range(h)]
        while len(q) > qi:
            i,j = q[qi]
            qi += 1
            for di,dj in d:
                ni = di + i
                nj = dj + j
                if 0 <= ni < h and 0 <= nj < w and f[ni][nj] is None:
                    f[ni][nj] = 1
                    if a[ni][nj] == '.':
                        q.append((ni,nj))
                        b[ni][nj] = 1

        q = []
        for i in range(h):
            for j in range(w):
                if a[i][j] == 'W':
                    q.append((i,j))
        qi = 0
        f = [[None]*w for _ in range(h)]
        while len(q) > qi:
            i,j = q[qi]
            qi += 1
            for di,dj in d:
                ni = di + i
                nj = dj + j
                if 0 <= ni < h and 0 <= nj < w and f[ni][nj] is None:
                    f[ni][nj] = 1
                    if a[ni][nj] == '.':
                        q.append((ni,nj))
                        c[ni][nj] = 1
        bc = wc = 0
        for i in range(h):
            for j in range(w):
                if b[i][j] == 1 and c[i][j] == 0:
                    bc += 1
                elif c[i][j] == 1 and b[i][j] == 0:
                    wc += 1


        rr.append('{} {}'.format(bc,wc))

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
def bfs(i, j):
    if a[i][j] == ".":
        a[i][j] = "#"
    res=1
    wc=0
    bc=0
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            if (dx==0 and dy!=0) or (dx!=0 and dy==0):
                pass
            else:
                continue
            ny = i+dy
            nx = j+dx

            if 0<=nx<=w-1 and 0<=ny<=h-1 and a[ny][nx]!="#":
                if a[ny][nx] == ".":
                    wct, bct, rest = bfs(ny, nx)
                    wc+=wct
                    bc+=bct
                    res+=rest
                elif a[ny][nx]=="W":
                    wc+=1
                elif a[ny][nx]=="B":
                    bc+=1
    #print(wc, bc, res)
    return wc, bc, res

import sys
sys.setrecursionlimit(100000)

while True:
    w, h = map(int, input().split())
    wans = 0
    bans = 0
    if w==0 and h==0:
        break
    a = [list(input()) for _ in range(h)]

    for i in range(w):
        for j in range(h):
            if a[j][i] ==".":
                wc, bc, res = bfs(j, i)
                if wc>0 and bc==0:
                    wans+=res
                elif wc==0 and bc>0:
                    bans+=res
    print(bans, wans)

Submission status: Accepted

Solution code:
import sys
import math

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0:
        break
    field = [[-2 for i in xrange(h + 2)] for j in xrange(w + 2)]
    white = [[0 for i in xrange(h + 2)] for j in xrange(w + 2)]
    black = [[0 for i in xrange(h + 2)] for j in xrange(w + 2)]
    
    cand_white = []
    cand_black = []
    for i in xrange(h):
        line = raw_input()
        for j in xrange(w):
            if line[j] == 'W':
                field[j + 1][i + 1] = 1
                cand_white.append((j + 1, i + 1))
            elif line[j] == 'B':
                field[j + 1][i + 1] = -1
                cand_black.append((j + 1, i + 1))
            else:
                field[j + 1][i + 1] = 0
    next = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    while len(cand_white) > 0:
        cur_x, cur_y = cand_white.pop()
        for n_x, n_y in next:
            if field[cur_x + n_x][cur_y + n_y] == 0 and white[cur_x + n_x][cur_y + n_y] == 0:
                cand_white.append((cur_x + n_x, cur_y + n_y))
                white[cur_x + n_x][cur_y + n_y] = 1
    while len(cand_black) > 0:
        cur_x, cur_y = cand_black.pop()
        for n_x, n_y in next:
            if field[cur_x + n_x][cur_y + n_y] == 0 and black[cur_x + n_x][cur_y + n_y] == 0:
                cand_black.append((cur_x + n_x, cur_y + n_y))
                black[cur_x + n_x][cur_y + n_y] = 1
    count_black = 0
    count_white = 0
    for i in xrange(h):
        for j in xrange(w):
            if white[j + 1][i + 1] > black[j + 1][i + 1]:
                count_white += 1
            if black[j + 1][i + 1] > white[j + 1][i + 1]:
                count_black += 1
    print count_black, count_white

Submission status: Accepted

Solution code:
from collections import deque

while True:

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

    if W == 0 and H == 0:
        break

    a = []

    for i in range(H):

        A = list(input())
        a.append(A)

    q = deque([])

    for i in range(H):
        for j in range(W):

            if a[i][j] in ["W","B"]:
                q.append([i,j])

    while len(q) > 0:

        now = q.pop()
        nx = now[0]
        ny = now[1]

        if a[nx][ny] in[ "W","X" ]:

            if nx - 1 >= 0 and a[nx-1][ny] == ".":
                a[nx-1][ny] = "X"
                q.append([nx-1,ny])

            if ny - 1 >= 0 and a[nx][ny-1] == ".":
                a[nx][ny-1] = "X"
                q.append([nx,ny-1])

            if nx + 1 < H and a[nx+1][ny] == ".":
                a[nx+1][ny] = "X"
                q.append([nx+1,ny])

            if ny + 1 < W and a[nx][ny+1] == ".":
                a[nx][ny+1] = "X"
                q.append([nx,ny+1])


        if a[nx][ny] in ["B","C"]:

            if nx - 1 >= 0 and a[nx-1][ny] == ".":
                a[nx-1][ny] = "C"
                q.append([nx-1,ny])

            if ny - 1 >= 0 and a[nx][ny-1] == ".":
                a[nx][ny-1] = "C"
                q.append([nx,ny-1])

            if nx + 1 < H and a[nx+1][ny] == ".":
                a[nx+1][ny] = "C"
                q.append([nx+1,ny])

            if ny + 1 < W and a[nx][ny+1] == ".":
                a[nx][ny+1] = "C"
                q.append([nx,ny+1])

        if a[nx][ny] in ["B","C","Z"]:

            if nx - 1 >= 0 and a[nx-1][ny] == "X":
                a[nx-1][ny] = "Z"
                q.append([nx-1,ny])

            if ny - 1 >= 0 and a[nx][ny-1] == "X":
                a[nx][ny-1] = "Z"
                q.append([nx,ny-1])

            if nx + 1 < H and a[nx+1][ny] == "X":
                a[nx+1][ny] = "Z"
                q.append([nx+1,ny])

            if ny + 1 < W and a[nx][ny+1] == "X":
                a[nx][ny+1] = "Z"
                q.append([nx,ny+1])


        if a[nx][ny] in ["W","X","Z"]:

            if nx - 1 >= 0 and a[nx-1][ny] == "C":
                a[nx-1][ny] = "Z"
                q.append([nx-1,ny])

            if ny - 1 >= 0 and a[nx][ny-1] == "C":
                a[nx][ny-1] = "Z"
                q.append([nx,ny-1])

            if nx + 1 < H and a[nx+1][ny] == "C":
                a[nx+1][ny] = "Z"
                q.append([nx+1,ny])

            if ny + 1 < W and a[nx][ny+1] == "C":
                a[nx][ny+1] = "Z"
                q.append([nx,ny+1])

    bn = 0
    wn = 0
    for i in range(H):

        #print (a[i])

        for j in range(W):

            if a[i][j] == "C":
                bn += 1
            elif a[i][j] == "X":
                wn += 1
    
    print (bn,wn)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def dfs(x,y):
    global st
    global visited
    global ans

    if MAP[y][x] == '#':
        ans |= 0
        return
    elif MAP[y][x] == 'B':
        ans |= 1
        return
    elif MAP[y][x] == 'W':
        ans |= 2
        return
    else:
        visited[y][x] = True
        st.add((x,y))
        if not visited[y][x+1]:
            dfs(x+1,y)
        if not visited[y][x-1]:
            dfs(x-1,y)
        if not visited[y+1][x]:
            dfs(x,y+1)
        if not visited[y-1][x]:
            dfs(x,y-1)
        return

while True:
    W,H = inpl()
    if W == 0:
        break
    else:
        MAP = []
        MAP.append(['#']*(W+2))
        for _ in range(H):
            MAP.append(['#']+list(input())+['#'])
        MAP.append(['#']*(W+2))

        visited = [[False]*(W+2) for _ in range(H+2)]
        dp = [[-1]*(W+2) for _ in range(H+2)]
        ansb = answ = 0
        for y0 in range(1,H+1):
            for x0 in range(1,W+1):
                if not visited[y0][x0]:
                    st = set([])
                    ans = 0
                    dfs(x0,y0)
                    for x,y in st:
                        dp[y][x] = ans

        #for d in dp:
        #    print(' '.join([str(k).rjust(2) for k in d]))

        answ = ansb = 0
        for d in dp:
            answ += d.count(2)
            ansb += d.count(1)

        print(ansb,answ)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(y,x):
    q = deque()
    q.append((y,x))
    bfs_map[y][x] = 0
    res = 0
    su = 1
    while q:
        y,x = q.popleft()
        for dy,dx in d:
            y_ = y+dy
            x_ = x+dx
            if 0 <= y_ < h and 0 <= x_ < w:
                res |= f[s[y_][x_]]
                if bfs_map[y_][x_]:
                    bfs_map[y_][x_] = 0
                    if not f[s[y_][x_]]:
                        q.append((y_,x_))
                        su += 1
    return res,su
d = [(1,0),(-1,0),(0,1),(0,-1)]
while 1:
    w,h = map(int, input().split())
    if w == h == 0:
        break
    s = [input() for i in range(h)]
    bfs_map = [[1 for j in range(w)] for i in range(h)]
    f = {".":0, "B":1, "W":2}
    ans = [0,0,0,0]
    for y in range(h):
        for x in range(w):
            if bfs_map[y][x] and s[y][x] == ".":
                k,su = bfs(y,x)
                ans[k] += su
    print(*ans[1:3])