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:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10000000)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count=0
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in ['@','#','*']:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line,values=input().strip(),list()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		value = list()
		for _ in range(H):
			value.append(list(x for x in input().strip()))
		values.append(value)
		line = input().strip()
	for value in values:
		print(solve(value))

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# coding: utf-8
# @????????? #?????? *?????????
import sys
sys.setrecursionlimit(1000000)

def dfs(x, y, fru):
    # ???????????¨?????????.???????????????
    field[x][y] = '.'
    # 4??????????????????
    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)

#x,y??§2??¶?????°???1?????§??\????????????????????\???????????°?????§????????¨???
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: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10000000)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line,values=input().strip(),list()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		value = list()
		for _ in range(H):
			value.append(list(x for x in input().strip()))
		values.append(value)
		line = input().strip()
	for value in values:
		print(solve(value))

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line,values=input().strip(),list()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		value = list()
		for _ in range(H):
			value.append(list(x for x in input().strip()))
		values.append(value)
		line = input().strip()
	for value in values:
		print(solve(value))

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# coding: utf-8
# @????????? #?????? *?????????
import sys
sys.setrecursionlimit(10000000)

def dfs(x, y, fru):
    # ???????????¨?????????.???????????????
    field[x][y] = '.'
    # 4??????????????????
    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,field[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: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


def process():
    for data in get_dataset():
        H = len(data)
        W = len(data[0])
        field = create_field(H, W)
        print search(H, W, data, field)


def search(H, W, data, field):
    count = 0
    for i in xrange(H):
        for j in xrange(W):
            if field[i][j] == 0:
                continue
            _search(i, j, H, W, data[i][j], data, field)
            count += 1
    return count


def _search(i, j, H, W, cell, data, field):
    field[i][j] = 0
    for a in xrange(i-1, i+2):
        if -1 < a < H:
            pass
        else:
            continue
        for b in xrange(j-1, j+2):
            if -1 < b < W:
                pass
            else:
                continue

            if a != i and b != j:
                continue

            if field[a][b] == 0:
                continue
            if cell == data[a][b]:
                _search(a, b, H, W, cell, data, field)
    return


def create_field(H, W):
    field = []
    for i in xrange(H):
        raw = []
        for j in xrange(W):
            raw.append(1)
        field.append(raw)
    return field


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(raw_input().rstrip())
        dataset.append(data)
    return dataset

process()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)


def process():
    for data in get_dataset():
        H = len(data)
        W = len(data[0])
        field = create_field(H, W)
        print search(H, W, data, field)


def search(H, W, data, field):
    count = 0
    for i in xrange(H):
        for j in xrange(W):
            if field[i][j] == 0:
                continue
            _search(i, j, H, W, data[i][j], data, field)
            count += 1
    return count


def _search(i, j, H, W, cell, data, field):
    field[i][j] = 0
    for a in xrange(i-1, i+2):
        if -1 < a < H:
            pass
        else:
            continue
        for b in xrange(j-1, j+2):
            if -1 < b < W:
                pass
            else:
                continue

            if a != i and b != j:
                continue

            if field[a][b] == 0:
                continue
            if cell == data[a][b]:
                _search(a, b, H, W, cell, data, field)
    return


def create_field(H, W):
    field = []
    for i in xrange(H):
        raw = []
        for j in xrange(W):
            raw.append(1)
        field.append(raw)
    return field


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(raw_input().rstrip())
        dataset.append(data)
    return dataset

process()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)


def process():
    for data in get_dataset():
        H = len(data)
        W = len(data[0])
        print search(H, W, data)


def search(H, W, data):
    count = 0
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if -1 < a < H:
            pass
        else:
            continue
        for b in xrange(j-1, j+2):
            if -1 < b < W:
                pass
            else:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue
            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return

def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset

process()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def load_fields():
	fields = []
	i = 0
	H, W = 0, 0
	field = []
	for line in sys.stdin:
		line = line.rstrip()
		if line[0] not in ["#", "@", "*"]:
			line = line.split(" ")
			H = int(line[0])
			W = int(line[1])
			if (len(field) != 0):
				fields.append(field)
				field = []
			if (H == 0 and W == 0):
				break

		else:
			field.append(list(line))
		i += 1
	return fields

def dfs(x, y, fruit):
	field[x][y] = "0"
	for dx in [-1, 0, 1]:
		if dx == -1: width = [0]
		if dx == 0: width = [-1, 0, 1]
		if dx == 1: width = [0]
		for dy in width:
			nx = x+dx
			ny = y+dy
			inField = (0 <= nx) and (0 <= ny) and (nx < H) and (ny < W)
			if inField and field[nx][ny] == fruit:
				dfs(nx, ny, fruit)
				
fields = load_fields()
count = 0
for field in fields:
	H = len(field)
	W = len(field[0])
	for x in range(H):
		for y in range(W):
			if (field[x][y] != "0"):
				dfs(x, y, field[x][y])
				count += 1
	print(count)
	count = 0

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)


def main():
    process()


def process():
    for data in get_dataset():
        print search(data)


def search(data):
    count = 0
    H = len(data)
    W = len(data[0])
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if -1 < a < H:
            pass
        else:
            continue
        for b in xrange(j-1, j+2):
            if -1 < b < W:
                pass
            else:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue
            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)


def main():
    solve()


def solve():
    for data in get_dataset():
        print search(data)


def search(data):
    count = 0
    H = len(data)
    W = len(data[0])
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if not -1 < a < H:
            continue
        for b in xrange(j-1, j+2):
            if not -1 < b < W:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue
            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def load_fields():
	fields = []
	i = 0
	H, W = 0, 0
	field = []
	for line in sys.stdin:
		line = line.rstrip()
		if line[0] not in ["#", "@", "*"]:
			line = line.split(" ")
			H, W = int(line[0]), int(line[1])
			if (len(field) != 0):
				fields.append(field)
				field = []
			if (H == 0 and W == 0):
				break

		else:
			field.append(list(line))
		i += 1
	return fields

def dfs(x, y, fruit):
	field[x][y] = "0"
	for dx in [-1, 0, 1]:
		if dx == -1: width = [0]
		if dx == 0: width = [-1, 0, 1]
		if dx == 1: width = [0]
		for dy in width:
			nx = x+dx
			ny = y+dy
			inField = (0 <= nx < H) and (0 <= ny < W)
			if inField and (field[nx][ny] == fruit):
				dfs(nx, ny, fruit)

fields = load_fields()
count = 0
for field in fields:
	H = len(field)
	W = len(field[0])
	for x in range(H):
		for y in range(W):
			if (field[x][y] != "0"):
				dfs(x, y, field[x][y])
				count += 1
	print(count)
	count = 0

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)


def main():
    solve()


def solve():
    for data in get_dataset():
        print search(data)


def search(data):
    count = 0
    H = len(data)
    W = len(data[0])
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if not -1 < a < H:
            continue
        for b in xrange(j-1, j+2):
            if not -1 < b < W:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue

            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def setLine(tempH, line):
    for i in range(0, len(line)):
        geo[tempH][i] = line[i:i+1]

def solve():
    person = 0
    for i in range(0,H):
        for j in range(0,W):
            if geo[i][j] is not "_":
                search(i,j)
                person += 1
    print(person)

def search(i,j):
    temp = geo[i][j]
    geo[i][j] = "_"
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    for a in range(0,4):
        idx = i + dx[a]
        jdy = j + dy[a]
        if(isOnMap(idx, jdy)):
            if(isNeededToSolve(temp, idx, jdy)):
                search(idx,jdy)

def isOnMap(i,j):
    return (0<=i and 0<=j and i<H and j<W)

def isNeededToSolve(temp,i,j):
    target = geo[i][j]
    return (target is not "_" and temp is target)

limit = 10**7
sys.setrecursionlimit(limit)

H = -1
W = -1
tempH = 0
geo = [[0 for i in range(1)]for j in range(1)]
repeat = True
while repeat:
    line = input()
    if H is -1 and W is -1:
        H = int(line.split(" ")[0])
        W = int(line.split(" ")[1])
        geo = [[0 for i in range(W)] for j in range(H)]
    else:
        setLine(tempH, line)
        tempH+=1

    #break
    if H is 0 and W is 0:
        break

    #solve
    if tempH is H:
        solve()
        H = -1
        W = -1
        tempH = 0

Submission status: Accepted

Solution code:
import sys

def setLine(tempH, line):
    for i in range(0, len(line)):
        geo[tempH][i] = line[i:i+1]

def solve():
    person = 0
    for i in range(0,H):
        for j in range(0,W):
            if geo[i][j] is not "_":
                search(i,j)
                person += 1
    print(person)

def search(i,j):
    temp = geo[i][j]
    geo[i][j] = "_"
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    for a in range(0,4):
        idx, jdy = i + dx[a], j + dy[a]
        if(isOnMap(idx, jdy)):
            if(isNeededToSolve(temp, idx, jdy)):
                search(idx,jdy)

def isOnMap(i,j):
    return (0<=i and 0<=j and i<H and j<W)

def isNeededToSolve(temp,i,j):
    target = geo[i][j]
    return (target is not "_" and temp is target)

limit = 10**7
sys.setrecursionlimit(limit)
H, W, tempH = -1, -1, 0
geo = [[0 for i in range(1)]for j in range(1)]
while True:
    line = input()
    if H is -1 and W is -1:
        p = line.split(" ")
        H, W = int(p[0]), int(p[1])
        geo = [[0 for i in range(W)] for j in range(H)]
    else:
        setLine(tempH, line)
        tempH+=1

    #break
    if H is 0 and W is 0:
        break

    #solve
    if tempH is H:
        solve()
        H, W, tempH = -1, -1, 0

Submission status: Accepted

Solution code:
import sys

def setLine(tempH, line):
    for i in range(0, len(line)):
        geo[tempH][i] = line[i:i+1]

def solve():
    person = 0
    for i in range(0,H):
        for j in range(0,W):
            if geo[i][j] is not "_":
                search(i,j)
                person += 1
    print(person)

def search(i,j):
    temp = geo[i][j]
    geo[i][j] = "_"
    for a in range(0,4):
        idx, jdy = i + dx[a], j + dy[a]
        if(isOnMap(idx, jdy)):
            if(isNeededToSolve(temp, idx, jdy)):
                search(idx,jdy)

def isOnMap(i,j): return (0<=i and 0<=j and i<H and j<W)

def isNeededToSolve(temp,i,j):
    target = geo[i][j]
    return (target is not "_" and temp is target)

limit = 10**7
sys.setrecursionlimit(limit)

H, W, tempH = -1, -1, 0
dx = [-1,0,1,0]
dy = [0,-1,0,1]
geo = [[0 for i in range(1)]for j in range(1)]
while True:
    line = input()
    if H is -1 and W is -1:
        p = line.split(" ")
        H, W = int(p[0]), int(p[1])
        geo = [[0 for i in range(W)] for j in range(H)]
    else:
        setLine(tempH, line)
        tempH+=1
    if H is 0 and W is 0:break
    if tempH is H:
        solve()
        H, W, tempH = -1, -1, 0

Submission status: Accepted

Solution code:
import sys
def solve():
    person = 0
    for i in range(0,H):
        for j in range(0,W):
            if geo[i][j] is not "_":
                search(i,j)
                person += 1
    print(person)

def search(i,j):
    temp = geo[i][j]
    geo[i][j] = "_"
    for a in range(0,4):
        idx, jdy = i + dx[a], j + dy[a]
        if(isOnMap(idx, jdy)):
            if(isNeededToSolve(temp, idx, jdy)):
                search(idx,jdy)

def isOnMap(i,j): return (0<=i and 0<=j and i<H and j<W)

def isNeededToSolve(temp,i,j):
    target = geo[i][j]
    return (target is not "_" and temp is target)

limit = 10**7
sys.setrecursionlimit(limit)

H, W, tempH = -1, -1, 0
dx = [-1,0,1,0]
dy = [0,-1,0,1]
geo = [[0 for i in range(1)]for j in range(1)]
while True:
    line = input()
    if H is -1 and W is -1:
        p = line.split(" ")
        H, W = int(p[0]), int(p[1])
        geo = [[0 for i in range(W)] for j in range(H)]
    else:
        geo[tempH] = list(line)
        tempH+=1
    if H is 0 and W is 0:break
    if tempH is H:
        solve()
        H, W, tempH = -1, -1, 0

Submission status: Accepted

Solution code:
import sys
def solve():
    person = 0
    for i in range(0,H):
        for j in range(0,W):
            if geo[i][j] is not "_":
                temp = geo[i][j]
                search(i,j,temp)
                person += 1
    print(person)

def search(i,j,temp):
    geo[i][j] = "_"
    for a in range(0,4):
        idx, jdy = i + dx[a], j + dy[a]
        if(isOnMap(idx, jdy)):
            if(isNeededToSolve(temp, idx, jdy)):
                search(idx,jdy, temp)

def isOnMap(i,j): return (0<=i and 0<=j and i<H and j<W)

def isNeededToSolve(temp,i,j):
    target = geo[i][j]
    return (target is not "_" and temp is target)

limit = 10**7
sys.setrecursionlimit(limit)

H, W, tempH = -1, -1, 0
dx = [-1,0,1,0]
dy = [0,-1,0,1]
geo = [[0 for i in range(1)]for j in range(1)]
while True:
    line = input()
    if H is -1 and W is -1:
        p = line.split(" ")
        H, W = int(p[0]), int(p[1])
        geo = [[0 for i in range(W)] for j in range(H)]
    else:
        geo[tempH] = list(line)
        tempH+=1
    if H is 0 and W is 0:break
    if tempH is H:
        solve()
        H, W, tempH = -1, -1, 0

Submission status: Accepted

Solution code:
import sys
def solve():
    person = 0
    for i in range(0,H):
        for j in range(0,W):
            if geo[i][j] is not "_":
                search(i,j)
                person += 1
    print(person)
 
def search(i,j):
    temp = geo[i][j]
    geo[i][j] = "_"
    for a in range(0,4):
        idx, jdy = i + dx[a], j + dy[a]
        if(isOnMap(idx, jdy)):
            if(isNeededToSolve(temp, idx, jdy)):
                search(idx,jdy)
 
def isOnMap(i,j): return (0<=i and 0<=j and i<H and j<W)
 
def isNeededToSolve(temp,i,j):
    target = geo[i][j]
    return (target is not "_" and temp is target)
 
limit = 10**7
sys.setrecursionlimit(limit)
 
H, W, tempH = -1, -1, 0
dx = [-1,0,1,0]
dy = [0,-1,0,1]
geo = [[0 for i in range(1)]for j in range(1)]
while True:
    line = input()
    if H is -1 and W is -1:
        p = line.split(" ")
        H, W = int(p[0]), int(p[1])
        geo = [[0 for i in range(W)] for j in range(H)]
    else:
        geo[tempH] = list(line)
        tempH+=1
    if H is 0 and W is 0:break
    if tempH is H:
        solve()
        H, W, tempH = -1, -1, 0

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
#	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
#		search(values,hp+dh,vp+dv,item)
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line, values = input().strip(), list()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		value = list()
		for _ in range(H):
#			value.append(list(x for x in input().strip()))
			value.append(list(input().strip()))
		print(solve(value))
#		values.append(value)
		line = input().strip()
#	for value in values:
#		print(solve(value))

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
#	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
#		search(values,hp+dh,vp+dv,item)
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line, values = input().strip(), list()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		value = list()
		for _ in range(H):
			value.append(list(x for x in input().strip()))
#			value.append(list(input().strip()))
		print(solve(value))
#		values.append(value)
		line = input().strip()
#	for value in values:
#		print(solve(value))

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
#	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
#		search(values,hp+dh,vp+dv,item)
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		values = list()
		for _ in range(H):
			values.append(list(input().strip()))
		print(solve(values))
		line = input().strip()

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(values,hp+dh,vp+dv,item)
#	search(values,hp-1,vp,item)
#	search(values,hp+1,vp,item)
#	search(values,hp,vp-1,item)
#	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		values = list()
		for _ in range(H):
			values.append(list(input().strip()))
		print(solve(values))
		line = input().strip()

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(field,hp,vp,item):
	if not (0<=hp<len(field)): return
	if not (0<=vp<len(field[hp])): return
	if item!=field[hp][vp]: return
	field[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(field,hp+dh,vp+dv,item)
#	search(field,hp-1,vp,item)
#	search(field,hp+1,vp,item)
#	search(field,hp,vp-1,item)
#	search(field,hp,vp+1,item)

def solve(field):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] in valid_items:
				search(field,i,j,field[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		field = list()
		for _ in range(H):
			field.append(list(input().strip()))
		print(solve(field))
		line = input().strip()

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

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

for s in sys.stdin:
    H, W = map(int, s.split())
    if H == W == 0:
        break

    # map
    M = []
    for i in range(H):
        s = input().strip()
        M.append(s)

    # W x H white map
    A = [[None for i in range(W)] for j in range(H)]

    def drawable(x, y):
        if 0 <= x < W and 0 <= y < H and A[y][x] == None:
            return True
        else:
            return False

    color_num = 0

    def fill(x, y):
        global color_num

        Q = [(x, y)]
        while Q:
            p = Q.pop(0)
            _x = p[0]
            _y = p[1]
            A[_y][_x] = color_num
            for direction in directions:
                new_x = _x + direction[0]
                new_y = _y + direction[1]
                if drawable(new_x, new_y) and M[_y][_x] == M[new_y][new_x]:
                    A[new_y][new_x] = color_num
                    Q.append((new_x, new_y))

    for y in range(H):
        for x in range(W):
            if drawable(x, y):
                color_num += 1
                fill(x, y)

    print(color_num)