Problem:


Property Distribution

 タナカ氏が HW アールの果樹園を残して亡くなりました。果樹園は東西南北方向に H &times; W の区画に分けられ、区画ごとにリンゴ、カキ、ミカンが植えられています。タナカ氏はこんな遺言を残していました。

      果樹園は区画単位でできるだけ多くの血縁者に分けること。ただし、ある区画の東西南北どれかの方向にとなりあう区画に同じ種類の果物が植えられていた場合は、区画の境界が分からないのでそれらは 1 つの大きな区画として扱うこと。

 例えば次のような 3 &times; 10 の区画であれば ('リ'はリンゴ、'カ'はカキ、'ミ'はミカンを表す)

同じ樹がある区画の間の境界を消すと次のようになり、

 結局 10 個の区画、つまり 10 人で分けられることになります。

雪が降って区画の境界が見えなくなる前に分配を終えなくてはなりません。あなたの仕事は果樹園の地図をもとに分配する区画の数を決めることです。

果樹園の地図を読み込み、分配を受けられる血縁者の人数を出力するプログラムを作成してください。

Input

複数のデータセットが与えられます。各データセットは空白で区切られた H, W (H, W ≤ 100) を含む行から始まり、続いて H &times; W の文字からなる H 行の文字列が与えられます。この文字列には、リンゴを表す '@'、カキを表す '#'、ミカンを表す '*'、の 3 文字しか現れません。

入力はゼロが２つの行で終わります。データセットの数は 20 を超えません。

Output

各データセットごとに、分配を受ける人数を１行に出力してください。

Sample Input

10 10
####*****@
@#@@@@#*#*
@##***@@@*
#****#*@**
##@*#@@*##
*@@@@*@@@#
***#@*@##*
*@@@*@@##@
*@*#*@##**
@****#@@#@
0 0

Output for the Sample Input

33



Sample input:
10 10
####*****@
@#@@@@#*#*
@##***@@@*
#****#*@**
##@*#@@*##
*@@@@*@@@#
***#@*@##*
*@@@*@@##@
*@*#*@##**
@****#@@#@
0 0


Sample output:
33

Submission status: Accepted

Solution code:
'''
while True:
    a=[int(num)for num in input().split(' ')]
    if a[0]==0:break
    s=[]
    cnt=0
    def rep(r,c,nest):
        global cnt
        f=s[r][c]
        if f=='.':return
        s[r][c]='.'
        if r>0:
            if s[r-1][c]==f:rep(r-1,c,False)
        if r<a[0]-1:
            if s[r+1][c]==f:rep(r+1,c,False)
        if c>0:
            if s[r][c-1]==f:rep(r,c-1,False)
        if c<a[1]-1:
            if s[r][c+1]==f:rep(r,c+1,False)
        if nest==True:
            cnt+=1 
    for i in range(a[0]):
        s.append(list(input()))
    for i in range(a[0]):
        for j in range(a[1]):
            rep(i,j,True)
    print(cnt)
'''
import queue
dr=[0,0,1,-1]
dc=[1,-1,0,0]
while True:
    a=[int(num)for num in input().split(' ')]
    if a[0]==0:break
    s=[]
    cnt=0
    for i in range(a[0]):
        s.append(list(input()))
    q=queue.Queue()
    for i in range(a[0]):
        for j in range(a[1]):
            if s[i][j]=='.':continue
            f=s[i][j]
            l=[[i,j]]
            while len(l)!=0:
                next_depth=[]
                for cor in l:
                    for k in range(4):
                        r=cor[0]+dr[k]
                        c=cor[1]+dc[k]
                        if 0<=r<a[0] and 0<=c<a[1] and s[r][c]==f:
                            s[r][c]='.'
                            next_depth.append([r,c])
                l=next_depth
            cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
''' DFS(TLE)
while True:
    a=[int(num)for num in input().split(' ')]
    if a[0]==0:break
    s=[]
    cnt=0
    def rep(r,c,nest):
        global cnt
        f=s[r][c]
        if f=='.':return
        s[r][c]='.'
        if r>0:
            if s[r-1][c]==f:rep(r-1,c,False)
        if r<a[0]-1:
            if s[r+1][c]==f:rep(r+1,c,False)
        if c>0:
            if s[r][c-1]==f:rep(r,c-1,False)
        if c<a[1]-1:
            if s[r][c+1]==f:rep(r,c+1,False)
        if nest==True:
            cnt+=1 
    for i in range(a[0]):
        s.append(list(input()))
    for i in range(a[0]):
        for j in range(a[1]):
            rep(i,j,True)
    print(cnt)
'''
#
''' BFS(List)
import queue
dr=[0,0,1,-1]
dc=[1,-1,0,0]
while True:
    a=[int(num)for num in input().split(' ')]
    if a[0]==0:break
    s=[]
    cnt=0
    for i in range(a[0]):
        s.append(list(input()))
    q=queue.Queue()
    for i in range(a[0]):
        for j in range(a[1]):
            if s[i][j]=='.':continue
            f=s[i][j]
            l=[[i,j]]
            while len(l)!=0:
                next_depth=[]
                for cor in l:
                    for k in range(4):
                        r=cor[0]+dr[k]
                        c=cor[1]+dc[k]
                        if 0<=r<a[0] and 0<=c<a[1] and s[r][c]==f:
                            s[r][c]='.'
                            next_depth.append([r,c])
                l=next_depth
            cnt+=1
    print(cnt)
'''
#
''' BFS(Queue) '''
import queue
dr=[0,0,1,-1]
dc=[1,-1,0,0]
while True:
    a=[int(num)for num in input().split(' ')]
    if a[0]==0:break
    s=[]
    cnt=0
    for i in range(a[0]):
        s.append(list(input()))
    q=queue.Queue()
    for i in range(a[0]):
        for j in range(a[1]):
            if s[i][j]=='.':continue
            f=s[i][j]
            q.put([i,j])
            while not q.empty():
                cor=q.get()
                for k in range(4):
                    r=cor[0]+dr[k]
                    c=cor[1]+dc[k]
                    if 0<=r<a[0] and 0<=c<a[1] and s[r][c]==f:
                        s[r][c]='.'
                        q.put([r,c])
            cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118
"""
import sys



def solve(data):
    size = len(data[0])
    data.insert(0, ['0' for _ in range(size)])
    data.insert(len(data), ['0' for _ in range(size)])

    processing_area = []
    area_id = 0
    for y in range(1, len(data)):
        for x in range(1, len(data[0])):
            # print('y:{}, x:{}'.format(y, x))
            mark = data[y][x]
            data[y][x] = '0'
            if mark != '0':
                area_id += 1
                processing_area.append((y, x))

                while processing_area:
                    yy, xx = processing_area.pop()
                    if data[yy-1][xx] == mark:
                        data[yy-1][xx] = '0'
                        processing_area.append((yy-1, xx))
                    if data[yy+1][xx] == mark:
                        data[yy+1][xx] = '0'
                        processing_area.append((yy+1, xx))
                    if data[yy][xx-1] == mark:
                        data[yy][xx-1] = '0'
                        processing_area.append((yy, xx-1))
                    if data[yy][xx+1] == mark:
                        data[yy][xx+1] = '0'
                        processing_area.append((yy, xx+1))
                mark = '0'
    return area_id



def main(args):
    # data = []
    # data.append(['0', '#', '#', '#', '#', '*', '*', '*', '*', '*', '@', '0'])
    # data.append(['0', '@', '#', '@', '@', '@', '@', '#', '*', '#', '*', '0'])
    # data.append(['0', '@', '#', '#', '*', '*', '*', '@', '@', '@', '*', '0'])
    # data.append(['0', '#', '*', '*', '*', '*', '#', '*', '@', '*', '*', '0'])
    # data.append(['0', '#', '#', '@', '*', '#', '@', '@', '*', '#', '#', '0'])
    # data.append(['0', '*', '@', '@', '@', '@', '*', '@', '@', '@', '#', '0'])
    # data.append(['0', '*', '*', '*', '#', '@', '*', '@', '#', '#', '*', '0'])
    # data.append(['0', '*', '@', '@', '@', '*', '@', '@', '#', '#', '@', '0'])
    # data.append(['0', '*', '@', '*', '#', '*', '@', '#', '#', '*', '*', '0'])
    # data.append(['0', '@', '*', '*', '*', '*', '#', '@', '@', '#', '@', '0'])

    while True:
        h, w = [int(x) for x in input().split(' ')]
        if h == 0 and w == 0:
            break
        data = []
        for _ in range(h):
            temp = list(input())
            temp.insert(0, '0')
            temp.append('0')
            data.append(temp)

        result = solve(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118
"""
import sys



def solve(data):
    size = len(data[0])
    data.insert(0, ['0' for _ in range(size)])
    data.insert(len(data), ['0' for _ in range(size)])

    processing_area = []
    area_id = 0
    for y in range(1, len(data)-1):
        for x in range(1, len(data[0])):
            # print('y:{}, x:{}'.format(y, x))
            mark = data[y][x]
            data[y][x] = '0'
            if mark != '0':
                area_id += 1
                processing_area.append((y, x))

                while processing_area:
                    yy, xx = processing_area.pop()
                    if data[yy-1][xx] == mark: #  ???
                        data[yy-1][xx] = '0'
                        processing_area.append((yy-1, xx))
                    if data[yy+1][xx] == mark: #  ???
                        data[yy+1][xx] = '0'
                        processing_area.append((yy+1, xx))
                    if data[yy][xx-1] == mark: #  ???
                        data[yy][xx-1] = '0'
                        processing_area.append((yy, xx-1))
                    if data[yy][xx+1] == mark: #  ???
                        data[yy][xx+1] = '0'
                        processing_area.append((yy, xx+1))
                mark = '0'
    return area_id



def main(args):
    # data = []
    # data.append(['0', '#', '#', '#', '#', '*', '*', '*', '*', '*', '@', '0'])
    # data.append(['0', '@', '#', '@', '@', '@', '@', '#', '*', '#', '*', '0'])
    # data.append(['0', '@', '#', '#', '*', '*', '*', '@', '@', '@', '*', '0'])
    # data.append(['0', '#', '*', '*', '*', '*', '#', '*', '@', '*', '*', '0'])
    # data.append(['0', '#', '#', '@', '*', '#', '@', '@', '*', '#', '#', '0'])
    # data.append(['0', '*', '@', '@', '@', '@', '*', '@', '@', '@', '#', '0'])
    # data.append(['0', '*', '*', '*', '#', '@', '*', '@', '#', '#', '*', '0'])
    # data.append(['0', '*', '@', '@', '@', '*', '@', '@', '#', '#', '@', '0'])
    # data.append(['0', '*', '@', '*', '#', '*', '@', '#', '#', '*', '*', '0'])
    # data.append(['0', '@', '*', '*', '*', '*', '#', '@', '@', '#', '@', '0'])

    while True:
        h, w = [int(x) for x in input().split(' ')]
        if h == 0 and w == 0:
            break
        data = []
        for _ in range(h):
            temp = list(input())
            temp.insert(0, '0')
            temp.append('0')
            data.append(temp)

        result = solve(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)

field = []
w = 0
h = 0


def main():
    global field, w, h
    while True:
        h, w = map(int, input().split())
        if h == 0 and w == 0:
            break
        count = 0
        field = []
        [field.append(list(input())) for _ in range(h)]
        for y in range(h):
            for x in range(w):
                if field[y][x] != -1:
                    dfs(field[y][x], x, y)
                    count += 1
        print(count)


def dfs(kind, x, y):
    global field
    field[y][x] = -1
    for dx, dy in zip([0, 0, -1, 1], [1, -1, 0, 0]):
        next_x = x + dx
        next_y = y + dy
        if next_x < 0 or next_y < 0 or next_x >= w or next_y >= h \
                or field[next_y][next_x] != kind:
            continue
        dfs(field[next_y][next_x], next_x, next_y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Labeling(terrain):

    label = terrain

    offset = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    signs = ["@", "#", "*"]
    step = 0

    for row in range(1, len(label) - 1):
        for col in range(1, len(label[row]) - 1):
            mark = label[row][col]

            if mark in signs:
                pointStack = [[row, col]]
                label[row][col] = step

                while 0 < len(pointStack):
                    rowIndex, colIndex = pointStack.pop()

                    for x, y in offset:
                        offsetRow, offsetCol = rowIndex + x, colIndex + y

                        if label[offsetRow][offsetCol] == mark:
                            pointStack.append([offsetRow, offsetCol])
                            label[offsetRow][offsetCol] = step

                step += 1

    return step


Sentinel = "1"

while True:
    col, row = [int(item) for item in input().split()]

    if row == 0 and col == 0:
        break

    land = []
    land.append([item for item in Sentinel * row + Sentinel * 2])

    for lp in range(col):
        part = [item for item in input()]
        land.append([])
        land[-1].extend([Sentinel])
        land[-1].extend(part)
        land[-1].extend([Sentinel])

    land.append([item for item in Sentinel * row + Sentinel * 2])

    result = Labeling(land)

    print(result)

Submission status: Accepted

Solution code:
def Labeling(terrain):

    label = terrain

    offset = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    signs = ["@", "#", "*"]
    rowLength, colLength = len(label) - 1, len(label[0]) - 1

    step = 0

    for row in range(1, rowLength):
        for col in range(1, colLength):
            mark = label[row][col]

            if mark in signs:
                pointStack = [[row, col]]
                label[row][col] = step

                while 0 < len(pointStack):
                    rowIndex, colIndex = pointStack.pop()

                    for x, y in offset:
                        offsetRow, offsetCol = rowIndex + x, colIndex + y

                        if label[offsetRow][offsetCol] == mark:
                            pointStack.append([offsetRow, offsetCol])
                            label[offsetRow][offsetCol] = step

                step += 1

    return step


Sentinel = "1"

while True:
    col, row = [int(item) for item in input().split()]

    if row == 0 and col == 0:
        break

    land = []
    land.append([item for item in Sentinel * row + Sentinel * 2])

    for lp in range(col):
        part = [item for item in input()]
        land.append([])
        land[-1].extend([Sentinel])
        land[-1].extend(part)
        land[-1].extend([Sentinel])

    land.append([item for item in Sentinel * row + Sentinel * 2])

    result = Labeling(land)

    print(result)

Submission status: Accepted

Solution code:
def Labeling(terrain):

    label = terrain

    offset = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    signs = ["@", "#", "*"]
    rowLength, colLength = len(label) - 1, len(label[0]) - 1

    step = 0

    for row in range(1, rowLength):
        for col in range(1, colLength):
            mark = label[row][col]

            if mark in signs:
                pointStack = [[row, col]]
                label[row][col] = step

                while 0 < len(pointStack):
                    rowIndex, colIndex = pointStack.pop()

                    for x, y in offset:
                        offsetRow, offsetCol = rowIndex + x, colIndex + y

                        if label[offsetRow][offsetCol] == mark:
                            pointStack.append([offsetRow, offsetCol])
                            label[offsetRow][offsetCol] = step

                step += 1

    return step


Sentinel = "1"

while True:
    col, row = [int(item) for item in input().split()]

    if row == 0 and col == 0:
        break

    land = []
    sentinels = [item for item in Sentinel * row + Sentinel * 2]
    land.append(sentinels)

    for lp in range(col):
        part = [item for item in input()]
        part = [Sentinel] + part + [Sentinel]
        land.append(part)

    land.append(sentinels)

    result = Labeling(land)

    print(result)

Submission status: Accepted

Solution code:
def solution():
    while True:
        m, n = [int(val) for val in raw_input().split()]
        if (m, n) == (0, 0):
            break
        mat = []
        for _ in range(m):
            mat.append(list(raw_input()))

        def dfs(x, y):
            direct = [-1, 0, 1, 0, -1]
            stk = []
            c = mat[x][y]
            if mat[x][y] != '.':
                stk.append((x, y))
                mat[x][y] = '.'
            while len(stk):
                x, y = stk.pop(-1)
                for i in range(4):
                    xx = x + direct[i]
                    yy = y + direct[i + 1]
                    if 0 <= xx < m and 0 <= yy < n and mat[xx][yy] == c:
                        stk.append((xx, yy))
                        mat[xx][yy] = '.'

        def solve():
            ans = 0
            for i in range(m):
                for j in range(n):
                    if mat[i][j] != '.':
                        ans += 1
                        dfs(i, j)
            print ans

        solve()


solution()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(20000)

def search(table, visited, i, j, c):
    visited[i][j] = True

    if table[i+1][j] == c and visited[i+1][j] == False:
        search(table, visited, i+1, j, c)
    if table[i-1][j] == c and visited[i-1][j] == False:
        search(table, visited, i-1, j, c)
    if table[i][j+1] == c and visited[i][j+1] == False:
        search(table, visited, i, j+1, c)
    if table[i][j-1] == c and visited[i][j-1] == False:
        search(table, visited, i, j-1, c)


while True:
    H,W = [int(i) for i in input().split()]
    if H == 0 and W == 0:
        break

    visited = [[False for i in range(W+2)] for j in range(H+2)]
    table = [["." for i in range(W+2)] for j in range(H+2)]

    for i in range(1,H+1):
        s = input()
        for j in range(1,W+1):
            table[i][j] = s[j-1]

    ans = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            if visited[i][j] == False:
                ans += 1
                search(table, visited, i, j, table[i][j])

    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

while True:
  h, w = map(int, input().split())
  if not h:
    break

  mp = [list("X" + input() + "X") for _ in range(h)]
  mp.insert(0, ["X"] * (w + 2))
  mp.append(["X"] * (w + 2))
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def search(x, y, target):
    mp[y][x] = "X"
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if mp[ny][nx] == target:
        search(nx, ny, target)
  
  ans = 0

  for x in range(1, w + 1):
    for y in range(1, h + 1):
      target = mp[y][x]
      if target != "X":
        search(x, y, target)
        ans += 1
  
  print(ans)

Submission status: Accepted

Solution code:
# AOJ 0118 Property Distribution 
# Python3 2018.6.23 bal4u
# 隣接する同種ものを集める、Unionセットに帰着

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

while 1:
	H, W = map(int, input().split())
	if H == 0 and W == 0: break
	tbl = ['']*H
	for r in range(H): tbl[r] = list(input())
	u = UnionSet(H*W)
	for r in range(H):
		for c in range(W):
			if c+1 < W and tbl[r][c] == tbl[r][c+1]: u.unite(r*W+c, r*W+c+1)
			if r+1 < H and tbl[r][c] == tbl[r+1][c]: u.unite(r*W+c, (r+1)*W+c)
	ans = 0
	for k in range(H*W):
		if u.root(k) == k: ans += 1
	print(ans)

Submission status: Accepted

Solution code:
# AOJ 0118 Property Distribution 
# Python3 2018.6.23 bal4u
# 隣接する同種ものを集める、Unionセットに帰着

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

while 1:
	H, W = map(int, input().split())
	if H == 0 and W == 0: break
	tbl = ['']*H
	for r in range(H): tbl[r] = input()
	u = UnionSet(H*W)
	rr = 0
	for r in range(H):
		for c in range(W):
			if c+1 < W and tbl[r][c] == tbl[r][c+1]: u.unite(rr+c, rr+c+1)
			if r+1 < H and tbl[r][c] == tbl[r+1][c]: u.unite(rr+c, rr+W+c)
		rr += W
	ans = 0
	for k in range(H*W):
		if u.root(k) == k: ans += 1
	print(ans)

Submission status: Accepted

Solution code:
mp = ["" for j in range(102)]
f = [[1 for i in range(102)] for j in range(102)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
while 1:
    H, W = map(int, raw_input().split())
    if H==0 and W==0 : break;
    mp[0] = mp[H+1] = "X"*(W+2);
    for i in range(1, H+1):
        mp[i] = "X"+raw_input()+"X"
        for j in range(1, W+1):
            f[i][j] = 0
    s = []; ans = 0;
    for i in range(1, H+1):
        for j in range(1, W+1):
            if f[i][j]==0:
                ans+=1; c = mp[i][j];
                s.append([j, i])
                while len(s)>0:
                    x, y = s.pop()
                    f[y][x] = 1
                    for k in range(4):
                        if mp[y+dy[k]][x+dx[k]]==c and f[y+dy[k]][x+dx[k]]==0:
                            s.append([x+dx[k], y+dy[k]])
    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

while True:
  h, w = map(int, input().split())
  if not h:
    break

  mp = [list("X" + input() + "X") for _ in range(h)]
  mp.insert(0, ["X"] * (w + 2))
  mp.append(["X"] * (w + 2))
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def search(x, y, target):
    mp[y][x] = "X"
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if mp[ny][nx] == target:
        search(nx, ny, target)
  
  ans = 0

  for x in range(1, w + 1):
    for y in range(1, h + 1):
      target = mp[y][x]
      if target != "X":
        search(x, y, target)
        ans += 1
  
  print(ans)

Submission status: Accepted

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():

    for _ in range(22):
        h, w = ZZ()
        if h == 0 and w == 0: break
        A = [input() for _ in range(h)]
        D = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        done = [[False] * w for _ in range(h)]
        ans = 0

        def dfs(x, y, fluit):
            if done[x][y]: return
            done[x][y] = True
            for dx, dy in D:
                nx, ny = x+dx, y+dy
                if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == fluit: dfs(nx, ny, fluit)

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

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 参考:http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3701512#1
import sys
sys.setrecursionlimit(100000)

dir = ((0, 1), (0, -1), (1, 0), (-1, 0))
def search(x, y, target):
    mp[y][x] = "X"
    for dx, dy in dir:
      nx = x + dx
      ny = y + dy
      if mp[ny][nx] == target:
        search(nx, ny, target)

while True:
  h, w = map(int, input().split())
  if h == 0:
    break

  mp = [list("X" + input() + "X") for _ in range(h)]
  mp.insert(0, ["X"] * (w + 2))
  mp.append(["X"] * (w + 2))
  ans = 0
 
  for x in range(1, w + 1):
    for y in range(1, h + 1):
      target = mp[y][x]
      if target != "X":
        search(x, y, target)
        ans += 1
  print(ans)

Submission status: Accepted

Solution code:



def calc(H,W,property):
    visit=[[False for i in range(W+2)] for j in range(H+2)]
    retval=0

    _property=[['.' for i in range(W+2)]]
    for p in property:
        _property.append(['.']+p+['.'])
    _property.append(['.' for i in range(W+2)])
    property=_property
    for i in range(1,H+1):
        for j in range(1,W+1):
            if visit[i][j]:
                continue
            visit[i][j]=True
            retval+=1
            next=[(i,j)]
            while len(next)>0:
                _next=[]
                for p in next:
                    if visit[p[0]-1][p[1]]==False and property[p[0]][p[1]]==property[p[0]-1][p[1]]:
                        _next.append((p[0]-1,p[1]))
                        visit[p[0]-1][p[1]]=True
                    if visit[p[0]+1][p[1]]==False and property[p[0]][p[1]]==property[p[0]+1][p[1]]:
                        _next.append((p[0]+1,p[1]))
                        visit[p[0]+1][p[1]]=True
                    if visit[p[0]][p[1]-1]==False and property[p[0]][p[1]]==property[p[0]][p[1]-1]:
                        _next.append((p[0],p[1]-1))
                        visit[p[0]][p[1]-1]=True
                    if visit[p[0]][p[1]+1]==False and property[p[0]][p[1]]==property[p[0]][p[1]+1]:
                        _next.append((p[0],p[1]+1))
                        visit[p[0]][p[1]+1]=True
                next=_next
    return retval




while True:
    H,W=[int(i) for i in input().split(" ")]
    if H==0 and W==0:
        break
    property=[[s for s in input()] for i in range(H)]
    print(calc(H,W,property))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def solve(x, y, char):
    for deltaX in [1, -1]:
        if 0 <= x + deltaX and x + deltaX < w and matrix[y][x + deltaX] == char:
            matrix[y][x + deltaX] = "."
            solve(x+deltaX, y, char)

    for deltaY in [1, -1]:
        if 0 <= y + deltaY and y + deltaY < h and matrix[y + deltaY][x] == char:
            matrix[y+deltaY][x] = "."
            solve(x, y+deltaY, char)


while (True):
    line = sys.stdin.readline().rstrip()
    if line == "" or line == "0 0":
        break

    h, w = (int(i) for i in line.split())

    matrix = []
    count = 0
    for i in range(h):
        matrix.append(list(input().rstrip()))

    for j, row in enumerate(matrix):
        for i, cell in enumerate(row):
            char = matrix[j][i]
            if (char != "."):
                matrix[j][i] = "."
                count += 1
                solve(i, j, char)
    
    print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def count(h, w, fruits):
    if h < 0 or h >= H:
        return False
    if w < 0 or w >= W:
        return False
    if fruits == '_':
        return False
    if fruits != land[h][w]:
        return False
    land[h][w] = '_'
    count(h+1, w, fruits)
    count(h-1, w, fruits)
    count(h, w+1, fruits)
    count(h, w-1, fruits)

while True:

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

    if H == 0:
        break

    ans = 0

    land = [list(input()) for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if land[i][j] != '_':
                ans += 1
                count(i, j, land[i][j])

    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(20000)

while True:
    H, W = map(int, input().split())
    if H == W == 0:
        exit()
    orchard = [list(input()) for i in range(H)]

    def dfs(i, j, fruit):
        orchard[i][j] = '.'
        move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        for di, dj in move:
            if 0 <= i+di < H and 0 <= j+dj < W and orchard[i+di][j+dj] == fruit:
                dfs(i+di, j+dj, fruit)

    count = 0
    for i in range(H):
        for j in range(W):
            if orchard[i][j] != '.':
                count += 1
                dfs(i, j, orchard[i][j])
    print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)

def dfschain(L, i, j):
    if L[i][j] == " ":
        return
    else:
        P = L[i][j]
        L[i][j] = " "
    for k in [-1, 1]:
        ni = i + k
        if ni not in range(len(L)):
            continue
        if L[ni][j] == P:
            dfschain(L, ni, j)
    for k in [-1, 1]:
        nj = j + k
        if nj not in range(len(L[0])):
            continue
        if L[i][nj] == P:
            dfschain(L, i, nj)
    return

while True:
    line, row = [int(x) for x in input().split()]
    if line == 0 and row == 0:
        break

    L = []
    for _ in range(line):
        l = list(input())
        L.append(l)

    cnt=0

    for i in range(line):
        for j in range(row):
            if L[i][j] != " ":
                cnt += 1
                dfschain(L, i, j)
    #print(L)
    print(cnt)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    while True:
        H, W = map(int, f_i.readline().split())
        if H == 0:
            break
        
        mp = ['X'] * (W + 2)
        for i in range(H):
            mp += list('X' + f_i.readline().rstrip() + 'X')
        mp += ['X'] * (W + 2)
        
        direction = (W + 2, -W - 2, -1, 1)
        ans = 0
        for i in range(W + 3, (W + 2) * (H + 1), W + 2):
            for j in range(i, i + W):
                f = mp[j]
                if f != 'X':
                    mp[j] = 'X'
                    parcel = [j]
                    while parcel:
                        p = parcel.pop()
                        for d in direction:
                            adj = p + d
                            if mp[adj] == f:
                                parcel.append(adj)
                                mp[adj] = 'X'
                    ans += 1
        print(ans)

solve()

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(100000)
 
while True:
  h, w = map(int, input().split())
  if not h:
    break
 
  mp = [list("X" + input() + "X") for _ in range(h)]
  mp.insert(0, ["X"] * (w + 2))
  mp.append(["X"] * (w + 2))
   
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))
 
  def search(x, y, target):
    mp[y][x] = "X"
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if mp[ny][nx] == target:
        search(nx, ny, target)
   
  ans = 0
 
  for x in range(1, w + 1):
    for y in range(1, h + 1):
      target = mp[y][x]
      if target != "X":
        search(x, y, target)
        ans += 1
   
  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(1000000)
 
def dfs(x, y, fru):
    field[x][y] = '.'
    for dx in [-1,0,1]:
        nx = x + dx
        if 0 <= nx and nx < H and field[nx][y] == fru:
            dfs(nx,y,fru)
    for dy in [-1,0,1]:
        ny = y + dy
        if 0 <= ny and ny < W and field[x][ny] == fru:
            dfs(x,ny,fru)
 
def solv(H,W):
    count = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] == '@':
                dfs(i,j,'@')
                count+=1
            elif field[i][j] == '#':
                dfs(i,j,'#')
                count+=1
            elif field[i][j] == '*':
                dfs(i,j,'*')
                count+=1
    print(count)
 
f=0
while(f==0):
    H, W = map(int, input().split())
    if H != 0 and W != 0:
        field = []
        for i in range(H):
            field.append(list(input()))
        solv(H,W)
    else:
        f=1

Submission status: Runtime Error

Solution code:
def solve(c,h,w,count):
	if 0 <= h < H and 0 <= w < W:
		if c in "#@*" and c == A[h][w]:
			A[h][w] = count
			solve(c,h+1,w,count)
			solve(c,h-1,w,count)
			solve(c,h,w+1,count)
			solve(c,h,w-1,count)
while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0:
		break
	A = [list(raw_input()) for i in range(H)]
	count = 0
	for h in range(H):
		for w in range(W):
			if str(A[h][w]) in "#@*":
				solve(A[h][w],h ,w,count)
				count += 1
	print count

Submission status: Runtime Error

Solution code:
def solve(c,h,w,count):
	if 0 <= h < H and 0 <= w < W:
		if c in "#@*" and c == A[h][w]:
			A[h][w] = count
			solve(c,h+1,w,count)
			solve(c,h-1,w,count)
			solve(c,h,w+1,count)
			solve(c,h,w-1,count)

while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0:
		break
	A = [list(raw_input()) for i in range(H)]
	count = 0
	for h in range(H):
		for w in range(W):
			if str(A[h][w]) in "#@*":
				solve(A[h][w],h ,w,count)
				count += 1
	print count