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: Accepted

Solution code:
from collections import deque
dxy = [[0, 1], [1, 0], [-1, 0], [0, -1]]


def which(x, y, map):
    if(map[x][y] != "." ):
        return (True, 0)
    else:
        Q = deque()
        W, H = len(map[0]), len(map)
        map[x][y] = "#"
        Q.append((x, y))
        # 0は未定,1なら黒、2なら白, ３は無効
        Black, White = False, False
        res = 1
        while(len(Q) != 0):
            now = Q.popleft()
            for d in dxy:
                tx, ty = now[0]+d[0], now[1]+d[1]
                # 色判定もする
                if 0 <= tx <= H-1 and 0 <= ty <= W-1:
                    if map[tx][ty] == ".":
                        map[tx][ty] = "#"
                        res += 1
                        Q.append((tx, ty))
                    elif map[tx][ty] == "B":
                        Black = True
                    elif map[tx][ty] == "W":
                        White = True
    # 黒かどうかと、レス、無効ならTrue 0
    return (Black, res) if Black ^ White else (True, 0)




while(True):
    # .だけBFSする、Wにしかぶつからないで全部いけたらW
    W, H = [int(n) for n in input().split()]
    V = [[False for _ in range(W)]for __ in range(H)]
    if W+H == 0:
        break
    map = ["" for _ in range(H)]
    for i in range(H):
        map[i] = list(str(input()))
    b = 0
    w = 0
    for i in range(H):
        for j in range(W):
            Black, cnt = which(i, j, map)
            if Black:
                b += cnt
            else:
                w += cnt
    # for i in range(H):
    #     print(map[i])
    print(b, 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:
# coding: utf-8
import queue
while 1:
    w,h=map(int,input().split())
    if w==0:
        break
    field=[]
    for i in range(h):
        field.append(list(input()))
    B=0
    W=0
    for i in range(h):
        for j in range(w):
            if field[i][j]=='.':
                q=queue.Queue()
                q.put((i,j))
                check=set()
                d=0
                while not q.empty():
                    y,x=q.get()
                    if field[y][x]=='.':
                        field[y][x]='#'
                        d+=1
                    elif field[y][x]=='W':
                        check.add('W')
                        continue
                    elif field[y][x]=='B':
                        check.add('B')
                        continue
                    else:
                        continue
                    if 0<=y+1<h and 0<=x<w:
                        q.put((y+1,x))
                    if 0<=y-1<h and 0<=x<w:
                        q.put((y-1,x))
                    if 0<=y<h and 0<=x+1<w:
                        q.put((y,x+1))
                    if 0<=y<h and 0<=x-1<w:
                        q.put((y,x-1))
                if len(check)==2:
                    pass
                elif 'B' in check:
                    B+=d
                elif 'W' in check:
                    W+=d
    print(B,W)

Submission status: Runtime Error

Solution code:
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: Runtime Error

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

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: Runtime Error

Solution code:
def dfs(r, c, n):
    if board[r][c] == n:
        return
    if board[r][c] in 'WB':
        pile.append(board[r][c])
        return 
    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:
            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: Runtime Error

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
            



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: Runtime Error

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
            



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: Runtime Error

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
            



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: Runtime Error

Solution code:
from collections import Counter


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: Runtime Error

Solution code:
import sys
from collections import Counter

sys.set_coroutine_wrapper(2500)


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: Runtime Error

Solution code:

W = 0
H = 0
island = list()

NOT_SUR = 0
BLACK = 1
WHITE = 2

def read_island():
    island = list()
    w, h = map(int, raw_input().split())
    for i in xrange(h):
        line = raw_input()
        chars = list()
        for ch in line:
            chars.append(ch)
        island.append(chars)

    return w, h, island


dir_x = [0, 1, 0, -1] # up, right, down, left
dir_y = [-1, 0, 1, 0]

def check_ex_adj(x, y, color):
    global island

    if island[y][x] != ".":
        return False

    for i in xrange(4):
        next_x = x + dir_x[i]
        next_y = y + dir_y[i]
        if not (0 <= next_x < W) or not (0 <= next_y < H):
            continue

        if island[y + dir_y[i]][x + dir_x[i]] == color:
            return True

    for i in xrange(4):
        next_x = x + dir_x[i]
        next_y = y + dir_y[i]
        if not (0 <= next_x < W) or not (0 <= next_y < H):
            continue

        island[y][x] = "B" if color == "W" else "W"
        is_ex_adj = check_ex_adj(next_x, next_y, color)
        island[y][x] = "."
        if is_ex_adj:
            return is_ex_adj

    return False


def check_surrounded(x, y):
    is_adj_b = check_ex_adj(x, y, "B")
    is_adj_w = check_ex_adj(x, y, "W")

    if is_adj_b and not is_adj_w:
        return BLACK
    elif not is_adj_b and is_adj_w:
        return WHITE

    return NOT_SUR


def solve():
    global W
    global H
    global island
    while True:
        W, H, island = read_island()
        if W == 0 and H == 0:
            break

        black_area = 0
        white_area = 0
        for x in xrange(W):
            for y in xrange(H):
                surrounded_by = check_surrounded(x, y)
                if surrounded_by == NOT_SUR:
                    continue

                if surrounded_by == BLACK: # Black
                    black_area += 1
                elif surrounded_by == WHITE:
                    white_area += 1

        print "{} {}".format(black_area, white_area)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def fill(MAP,xy,stick):
    global w,h
    if stick=='B': sflag=0
    else: sflag=1
    x,y=(xy[0],xy[1])
    if MAP[y][x][sflag]==0: MAP[y][x][sflag]=1
    xlist=[1,-1,0,0]
    ylist=[0,0,1,-1]
    for dx,dy in zip(xlist,ylist):
        nx=x+dx
        ny=y+dy
        if 0<=nx<w and 0<=ny<h:
            if  MAP[ny][nx][0]==-1 or MAP[ny][nx][1]==-1:
                continue
            elif MAP[ny][nx][sflag]==0:
                fill(MAP,[nx,ny],stick)

def countMAP(MAP):
    global w,h
    countB=0
    countW=0
    for x in range(w):
        for y in range(h):
            if MAP[y][x]==[1,0]:
                countB+=1
            elif MAP[y][x]==[0,1]:
                countW+=1
    return countB,countW

while  True:
    w,h=map(int,input().split())
    if w==h==0: break
    MAP=[]
    for i in range(h):
        temp=input()
        MAP.append([])
        for j in range(w):
            if temp[j]=='.': MAP[i].append([0,0])
            elif temp[j]=='B': MAP[i].append([-1,0])
            else: MAP[i].append([0,-1])
    for y in range(h):
        for x in range(w):
            if MAP[y][x][0]==-1:
                fill(MAP,[x,y],'B')
            elif MAP[y][x][1]==-1:
                fill(MAP,[x,y],'W')
    countB,countW=countMAP(MAP)
    print(countB,countW)

Submission status: Runtime Error

Solution code:
dx=(1,-1,0,0)
dy=(0,0,1,-1)

def dfsW(y,x):
    if L[y][x]==".":
        L[y][x]="P"
    for i in range(4):
        mx=x+dx[i]
        my=y+dy[i]
        if 0<=mx<w and 0<=my<h and L[my][mx]==".":
            dfsW(my,mx)

def dfsB(y,x):
    if L[y][x]==".":
        L[y][x]="Q"
    elif L[y][x]=="P":
        L[y][x]="N"
    for i in range(4):
        mx=x+dx[i]
        my=y+dy[i]
        if 0<=mx<w and 0<=my<h and (L[my][mx]=="." or L[my][mx]=="P"):
            dfsB(my,mx)

while True:
    w,h=map(int,raw_input().split())
    if w==h==0:break
    L=[list(raw_input()) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if L[i][j]=="W":
                dfsW(i,j)
    for i in range(h):
        for j in range(w):
            if L[i][j]=="B":
                dfsB(i,j)
    cntW=cntB=0
    for i in range(h):
	cntW+=L[i].count("P")
	cntB+=L[i].count("Q")
    print cntB,cntW