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

Solution code:
print 'fw'

Submission status: Wrong Answer

Solution code:
import sys


print 0

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)


def process():
    data = []
    H = 0
    for line in get_data():
        line = line.split()
        if len(line) == 2:
            if line[0] == line[1] == '0':
                data = []
                continue
            H = int(line[0])
            W = int(line[1])
        elif len(line) == 1:
            data.append(line[0])
            if len(data) == H:
                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_data():
    return [line.strip() for line in raw_input()]


process()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

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)
print(fields)
count = 0
for field_info in fields:
	field = field_info[0]
	H = field_info[1]
	W = field_info[2]
	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: Wrong Answer

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

sys.setrecursionlimit(100000000)

def dfs(x, y, sym):
    field[x][y] = '.'
    for dx in range(-1,2):
        if dx==-1 or dx==1:
            nx = x + dx
            ny = y
            if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                dfs(nx, ny, sym)
        else:
            nx = x 
            for dy in [-1,1]:
                ny = y + dy
                if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                    dfs(nx, ny, sym)
def solve():
    res = 0
    flg=0 
    for i in range(N):
        for j in range(M):
            if not field[i][j] == '.':
                if field[i][j] == '@':
                    dfs(i, j, '@')
                    res += 1
                elif field[i][j] == '#':
                    dfs(i, j, '#')
                    res += 1
                else:
                    dfs(i, j, '*')
                    res += 1
    print(res)

Submission status: Wrong Answer

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

sys.setrecursionlimit(100000000)

def dfs(x, y, sym):
    field[x][y] = '.'
    for dx in range(-1,2):
        if dx==-1 or dx==1:
            nx = x + dx
            ny = y
            if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                dfs(nx, ny, sym)
        else:
            nx = x
            for dy in [-1,1]:
                ny = y + dy
                if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                    dfs(nx, ny, sym)
def solve():
    res = 0
    flg=0 
    for i in range(N):
        for j in range(M):
            if not field[i][j] == '.':
                if field[i][j] == '@':
                    dfs(i, j, '@')
                    res += 1
                elif field[i][j] == '#':
                    dfs(i, j, '#')
                    res += 1
                else:
                    dfs(i, j, '*')
                    res += 1
    print(res)

while True:
    datas = sys.stdin.readlines()
    print(datas)
    data = datas[0].split(' ')
    N = int(data[0])
    M = int(data[1])
    data2 = datas[-1].split(' ')
    L = int(data2[0])
    K = int(data2[1])
    if L==0 and K==0:
        break
    field = [[0 for i in range(N) ]for j in range(M)]

    for i in range(M):
        field[i] = list(datas[i+1])[0:-1]
    solve()

Submission status: Wrong Answer

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

sys.setrecursionlimit(100000000)

def dfs(x, y, sym):
    field[x][y] = '.'
    for dx in range(-1,2):
        if dx==-1 or dx==1:
            nx = x + dx
            ny = y
            if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                dfs(nx, ny, sym)
        else:
            nx = x
            for dy in [-1,1]:
                ny = y + dy
                if(nx>=0 and nx<N and 0<=ny and ny<M and field[nx][ny]==sym):
                    dfs(nx, ny, sym)
def solve():
    res = 0
    flg=0 
    for i in range(N):
        for j in range(M):
            if not field[i][j] == '.':
                if field[i][j] == '@':
                    dfs(i, j, '@')
                    res += 1
                elif field[i][j] == '#':
                    dfs(i, j, '#')
                    res += 1
                else:
                    dfs(i, j, '*')
                    res += 1
    print(res)

while True:
    datas = sys.stdin.readlines()
    data = datas[0].split(' ')
    N = int(data[0])
    M = int(data[1])
    data2 = datas[-1].split(' ')
    L = int(data2[0])
    K = int(data2[1])
    if L==0 and K==0:
        break
    field = [[0 for i in range(N) ]for j in range(M)]

    for i in range(M):
        field[i] = list(datas[i+1])[0:-1]
    solve()

Submission status: Wrong Answer

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 = map(int, line.split())
        value = list()
        for _ in range(H):
            value.append(list(input().strip()))
        print(solve(value))
        line = input().strip()

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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
    print(x, y, field[y][x])
    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: Wrong Answer

Solution code:
import sys

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


def dfs(x, y, c):
    judged[x][y] = True
    for dx, dy in d:
        if 0 <= x + dx < H and 0 <= y + dy < W and (not judged[x + dx][y + dy]) and orchard[x + dx][y + dy] == c:
            dfs(x + dx, y + dy, c)


if __name__ == '__main__':
    H, W = list(map(int, input().split()))
    if H == 0 and W == 0:
        sys.exit()

    orchard = [input() for i in range(H)]
    judged = [[False for i in range(W)] for j in range(H)]
    # print(orchard)
    ans = 0
    for i in range(0, H):
        for j in range(0, W):
            if not judged[i][j]:
                ans += 1
                dfs(i, j, orchard[i][j])

    print(ans)

Submission status: Wrong Answer

Solution code:
def solve(s,i,x,y):
	A[y][x] = i
	if x < W-1 and A[y][x+1] == s: solve(s,i,x+1,y)
	if y < H-1 and A[y+1][x] == s: solve(s,i,x,y+1)
	if x > 0   and A[y][x-1] == s: solve(s,i,x-1,y)
	if y > 0   and A[y-1][x] == s: solve(s,i,x,y-1)

# try-except is necessary
while 1:
	try:
		H,W = map(int,raw_input().split())
		if H == 0: break
		A = [list(raw_input()) for i in range(H)]
		i = 1
		for y in range(H):
			for x in range(W):
				if A[y][x] in ["#","@","*"]:
					solve(A[y][x],i,x,y)
					i += 1
		print max([max(A[i]) for i in range(H)])
	except:
		pass

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	A[y][x] = 0
	if x < W-1 and A[y][x+1] == s: fill0(s,x+1,y)
	if y < H-1 and A[y+1][x] == s: fill0(s,x,y+1)
	if x > 0   and A[y][x-1] == s: fill0(s,x-1,y)
	if y > 0   and A[y-1][x] == s: fill0(s,x,y-1)

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	print 0

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	A[y][x] = 0
	if x < W-1 and A[y][x+1] == s: fill0(s,x+1,y)
	if y < H-1 and A[y+1][x] == s: fill0(s,x,y+1)
	if x > 0   and A[y][x-1] == s: fill0(s,x-1,y)
	if y > 0   and A[y-1][x] == s: fill0(s,x,y-1)

while 1:
	try:
		H,W = map(int,raw_input().split())
		if H == 0: break
		A = [list(raw_input()) for i in range(H)]
		ans = 0
		for y in range(H):
			for x in range(W):
				if A[y][x] in ["#","@","*"]:
					fill0(A[y][x],x,y)
					ans += 1
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	A[y][x] = 0
	if x < W-1 and A[y][x+1] == s: fill0(s,x+1,y)
	if y < H-1 and A[y+1][x] == s: fill0(s,x,y+1)
	if x > 0   and A[y][x-1] == s: fill0(s,x-1,y)
	if y > 0   and A[y-1][x] == s: fill0(s,x,y-1)

while 1:
	try:
		H,W = map(int,raw_input().split())
		if H == 0: break
		A = [list(raw_input()) for i in range(H)]
		ans = 0
		for y in range(H):
			for x in range(W):
				if A[y][x] in ["#","@","*"]:
					fill0(A[y][x],x,y)
					ans += 1
		print ans
	except:
		pass

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	if 0 <= x <= W-1 and 0 <= y <= H-1 and A[y][x] == s:
		A[y][x] = 0
		fill0(s,x+1,y); fill0(s,x,y+1); fill0(s,x-1,y); fill0(s,x,y-1)
print 0

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	if 0 <= x <= W-1 and 0 <= y <= H-1 and A[y][x] == s:
		A[y][x] = 0
		fill0(s,x+1,y); fill0(s,x,y+1); fill0(s,x-1,y); fill0(s,x,y-1)
while 1:
        H,W = map(int,raw_input().split())
        break
print 1

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	print 0

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	if 0 <= x <= W-1 and 0 <= y <= H-1 and A[y][x] == s:
		A[y][x] = 0
		fill0(s,x+1,y); fill0(s,x,y+1); fill0(s,x-1,y); fill0(s,x,y-1)
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	ans = 0
	for y in range(H):
		for x in range(W):
			if A[y][x] in ["#","@","*"]:
			#	fill0(A[y][x],x,y)
				ans += 1
	print ans

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	A[y][x] = 0
	if x < W-1 and A[y][x+1] == s: fill0(s,x+1,y)
	if y < H-1 and A[y+1][x] == s: fill0(s,x,y+1)
	if x > 0   and A[y][x-1] == s: fill0(s,x-1,y)
	if y > 0   and A[y-1][x] == s: fill0(s,x,y-1)

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	ans = 0
	for y in range(H):
		for x in range(W):
			if A[y][x] in ["#","@","*"]:
				#fill0(A[y][x],x,y)
				ans += 1
	print ans

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	pass
#	A[y][x] = 0
#	if x < W-1 and A[y][x+1] == s: fill0(s,x+1,y)
#	if y < H-1 and A[y+1][x] == s: fill0(s,x,y+1)
#	if x > 0   and A[y][x-1] == s: fill0(s,x-1,y)
#	if y > 0   and A[y-1][x] == s: fill0(s,x,y-1)

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	ans = 0
	for y in range(H):
		for x in range(W):
			if A[y][x] in ["#","@","*"]:
				fill0(A[y][x],x,y)
				ans += 1
	print ans

Submission status: Time Limit Exceeded

Solution code:
def dfs(X,Y,ch):
	stack.append([X,Y])
	print stack
	field[X][Y] = '.'
	while len(stack) != 0:
		x,y = stack.pop()
		for i in range(4):
				nx = x+moveY[i]
				ny = y+moveX[i]
				if (nx >= 0 and ny >= 0) and(nx < H and ny < W) and field[nx][ny] == ch:
					if field[nx][ny] == '#' or field[nx][ny] == '*'or field[nx][ny] == '@':
						field[nx][ny] = '.'
						stack.append([nx,ny])
						print stack
stack = []
moveY = [-1,0,1,0]
moveX = [0,1,0,-1]
while True:
	H,W = map(int,raw_input().split(' '))
	if H == 0 and W == 0:
		break
	field = ['' for i in range(H)]
	h = 0
	for i in range(H):
		field[i] = list(raw_input())
	correct =0
	for i in range(H):
		for j in range(W):
			if field[i][j] == '@' or field[i][j] == '#'or field[i][j] == '*':
				dfs(i,j,field[i][j])
				correct += 1
	print correct

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys

sys.setrecursionlimit(20000)


matrix = []
vec = [[1,0],[-1,0],[0,1],[0,-1]]
visited =[]

def dfs(x,y,fruit):
  visited.append((x,y))
  for v in vec:
    nx = x + v[0]
    ny = y + v[1]
    if not (nx,ny) in visited and nx in xrange(w) and ny in xrange(h):
      if matrix[ny][nx] == fruit:
        dfs(nx,ny,fruit)



while True:
  h,w = map(int,raw_input().rstrip().split(" "))
  if h == 0 and w == 0:
    break
  matrix = []
  visited = []
  ans = 0
  for i in xrange(h):
    s = raw_input().rstrip()
    matrix.append(list(s))
  for i in xrange(h):
    for j in xrange(w):
      if not (j,i) in visited:
        dfs(j,i,matrix[i][j])
        ans+=1
  print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys

sys.setrecursionlimit(20000)


matrix = []
vec = [[1,0],[-1,0],[0,1],[0,-1]]
visited =[]
h = 0
w = 0

def dfs(x,y,fruit):
  visited.append((x,y))
  for v in vec:
    nx = x + v[0]
    ny = y + v[1]
    if (not (nx,ny) in visited) and nx in xrange(w) and ny in xrange(h):
      if matrix[ny][nx] == fruit:
        dfs(nx,ny,fruit)
  return 0


while True:
  h,w = map(int,raw_input().rstrip().split(" "))
  if h == 0 and w == 0:
    break
  matrix = []
  visited = []
  ans = 0
  for i in xrange(h):
    s = raw_input().rstrip()
    matrix.append(list(s))
  for i in xrange(h):
    for j in xrange(w):
      if not (j,i) in visited:
        dfs(j,i,matrix[i][j])
        ans+=1
  print ans

Submission status: Time Limit Exceeded

Solution code:
# Aizu Problem 0067: The Number of Islands
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


class UndirectedGraph():
    def __init__(self, grid):
        offsets = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        N = len(grid)
        M = len(grid[0])
        self.edges = {}
        self.nodes = []
        for row in range(N):
            for col in range(M):
                self.AddNode((row, col))
                for row_off, col_off in offsets:
                    row2 = row + row_off
                    col2 = col + col_off
                    if 0 <= row2 < N and 0 <= col2 < M and grid[row2][col2] == grid[row][col]:
                            self.AddEdge((row, col), (row2, col2))
        
    def AddNode(self, node):
        if node not in self.nodes:
            self.nodes.append(node)
        if node not in self.edges:
            self.edges[node] = []

    def GetNodes(self):
        return self.nodes

    def GetEdges(self):
        return self.edges

    def AddEdge(self, node1, node2):
        self.AddNode(node1)
        self.AddNode(node2)
        if node1 not in self.edges[node2]:
            self.edges[node2].append(node1)
        if node2 not in self.edges[node1]:
            self.edges[node1].append(node2)

    def Degree(self, node):
        return len(self.edges[node])

    def GetNeighbors(self, node):
        return self.edges.get(node, [])
            
    def GetPath(self, source, target):
        # find path by BFS:
        predecessor = {node: -1 for node in self.GetNodes()}
        predecessor[source] = 0
        visited = {node: False for node in self.GetNodes()}
        queue = [source]
        while len(queue) > 0:
            current = queue.pop(0)
            visited[current] = True
            for neighbor in self.GetNeighbors(current):
                if not visited[neighbor] and neighbor not in queue:
                    queue.append(neighbor)
                    predecessor[neighbor] = current
                if neighbor == target:
                    queue = []
                    break
        # build path from predecessor info:
        if predecessor[target] == -1:
            return []
        path = [target]
        while path[0] != source:
            path = [predecessor[path[0]]] + path[:]
        return path

    def GetConnectedComponents(self):
        # identify connected components by BFS
        nodes = self.GetNodes()[:]
        connected_components = []
        while len(nodes) > 0:
            queue = [nodes.pop()]
            component = [queue[0]]
            while len(queue) > 0:
                current = queue.pop(0)
                for neighbor in self.GetNeighbors(current):
                    if neighbor in nodes and neighbor not in queue:
                        queue.append(neighbor)
                        nodes.remove(neighbor)
                        component.append(neighbor)
            connected_components.append(component)
        return connected_components


while True:
    H, W = [int(_) for _ in input().split()]
    if H == W == 0:
        break
    grid = [input().strip() for _ in range(H)]
    G = UndirectedGraph(grid)
    print(len(G.GetConnectedComponents()))

Submission status: Accepted

Solution code:
def f(y,x,c0):
  global A,M
  M.append([y,x])
  while M:
    y,x=M.pop()
    if A[y][x]==c0:
      A[y][x]='X'
      for dy,dx in [[0,-1],[0,1],[-1,0],[1,0]]:
        M.append([y+dy,x+dx])
  return 1

M=[]
while 1:
  H,W=map(int,raw_input().split())
  if H==W==0: break
  A=[['X' for _ in range(W+2)] for _ in range(H+2)]
  for i in range(H):
    A[i+1][1:W+1]=list(raw_input())
  c=0
  for i in range(1,H+1):
    for j in range(1,W+1):
      c0=A[i][j]
      if c0!='X': c+=f(i,j,c0)
  print c

Submission status: Accepted

Solution code:
def f(y,x,c0):
  M.append([y,x])
  while M:
    y,x=M.pop()
    if A[y][x]==c0:
      A[y][x]=' '
      for i,j in [[0,-1],[-1,0],[0,1],[1,0]]: M.append([y+i,x+j])
  return 1

M=[]
while 1:
  H,W=map(int,raw_input().split())
  if H==W==0: break
  A=[list(' '*(W+2)) for _ in range(H+2)]
  for i in range(H): A[i+1][1:W+1]=list(raw_input())
  c=0
  for i in range(1,H+1):
    for j in range(1,W+1):
      c0=A[i][j]
      if c0!=' ': c+=f(i,j,c0)
  print c

Submission status: Accepted

Solution code:
def f(y,x,a):
  M.append([y,x])
  while M:
    y,x=M.pop()
    if A[y][x]==a:
      A[y][x]=' '
      for i,j in [[0,-1],[-1,0],[0,1],[1,0]]: M.append([y+i,x+j])
  return 1

M=[]
while 1:
  H,W=map(int,raw_input().split())
  if H==W==0: break
  A=[list(' '*(W+2)) for _ in range(H+2)]
  for i in range(H): A[i+1][1:W+1]=list(raw_input())
  c=0
  for i in range(1,H+1):
    for j in range(1,W+1):
      a=A[i][j]
      if a!=' ': c+=f(i,j,a)
  print c

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)
def solve(h,w,count,c):
    if 0 <= h < H and 0 <= w < W and A[h][w] == c:
        A[h][w] = count
        for dh,dw in zip([1,0,-1,0],[0,1,0,-1]):
            solve(h+dh,w+dw,count,c)
while 1:
    H,W = map(int,raw_input().split())
    if H == W == 0: break
    A = [list(raw_input()) for _ in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if type(A[h][w]) is not int:
                solve(h,w,count,A[h][w])
                count += 1
    print count

Submission status: Accepted

Solution code:
def dfs(X,Y,ch):
	stack.append([X,Y])
	field[X][Y] = '.'
	while len(stack) > 0:
		x,y = stack.pop()
		for i in range(4):
				nx = x+moveY[i]
				ny = y+moveX[i]
				if nx < 0 or ny < 0 or nx >= H or ny >= W or field[nx][ny] != ch:
					continue
				if field[nx][ny] == '#' or field[nx][ny] == '*'or field[nx][ny] == '@':
					field[nx][ny] = '.'
					stack.append([nx,ny])
stack = []
moveY = [-1,0,1,0]
moveX = [0,1,0,-1]
while True:
	H,W = map(int,raw_input().split(' '))
	if H == 0 and W == 0:
		break
	field = [list(raw_input()) for i in range(H)]
	correct =0
	for i in range(H):
		for j in range(W):
			if field[i][j] == '@' or field[i][j] == '#'or field[i][j] == '*':
				dfs(i,j,field[i][j])
				correct += 1
	print correct

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)
def wa(h, w, f):
    if not (0 <= h < H and 0 <= w < W):
        return
    elif mapp[h][w] != f:
        return
    else:
        mapp[h][w] = '$'
        wa(h, w+1, f)
        wa(h-1, w, f)
        wa(h, w-1, f)
        wa(h+1, w, f)

while True:
    H, W = map(int, raw_input().split())
    if H == 0 and W == 0: break
    mapp = [list(raw_input()) for i in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if mapp[h][w] == '@':
                count += 1
                wa(h, w, '@')
            elif mapp[h][w] == '#':
                count += 1
                wa(h, w, '#')
            elif mapp[h][w] == '*':
                count += 1
                wa(h, w, '*')
    else:
        print count

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def check(x, y, flag):
	farm[x][y] = "$"
	if farm[x + 1][y] == flag : check(x + 1, y, flag)
	if farm[x - 1][y] == flag : check(x - 1, y, flag)
	if farm[x][y + 1] == flag : check(x, y + 1, flag)
	if farm[x][y - 1] == flag : check(x, y - 1, flag)
	return 1

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

	farm = []
	farm.append(list("$" * (w + 2)))
	for i in range(0, h):
		farm.append(list("$" + raw_input() + "$"))
	farm.append(list("$" * (w + 2)))
	
	count = 0
	for i in range(0, h):
		for j in range(0, w):
			if farm[i + 1][j + 1] != "$":
				count += check(i + 1, j + 1, farm[i + 1][j + 1])
				
	print count

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def check(x, y, flag):
	farm[x][y] = "$"
	if farm[x + 1][y] == flag : check(x + 1, y, flag)
	if farm[x - 1][y] == flag : check(x - 1, y, flag)
	if farm[x][y + 1] == flag : check(x, y + 1, flag)
	if farm[x][y - 1] == flag : check(x, y - 1, flag)
	return 1

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

	farm = []
	farm.append(list("$" * (w + 2)))
	for i in range(0, h):
		farm.append(list("$" + raw_input() + "$"))
	farm.append(list("$" * (w + 2)))
	
	count = 0
	for i in range(0, h):
		for j in range(0, w):
			if farm[i + 1][j + 1] != "$":
				count += check(i + 1, j + 1, farm[i + 1][j + 1])
				
	print count

Submission status: Accepted

Solution code:
h = w = 0
slist =[]
list1=[]
def dfs(f):
    while True:
        if len(slist) == 0:
            return 1
        coordinate= slist.pop()
        #print(coordinate)
        x = coordinate[0]
        y = coordinate[1]

        list1[y] = list1[y][:x] + '1' + list1[y][x + 1:]
        if x + 1 < w:
            if list1[y][x + 1] == f:
                slist.append([x + 1,y])
        if x - 1 >= 0:
            if list1[y][x-1] == f:
                slist.append([x - 1, y])
        if y + 1 < h:
            if list1[y + 1][x] == f:
                slist.append([x, y + 1])
        if y -1 >= 0:
            if list1[y -1][x] == f:
                slist.append([x, y - 1])

while True:
    h, w = list(map(lambda x: int(x),input().split(" ")))
    if 0 in (h, w):
        break
    n = 0
    for i in range(0, h):
        list1.append(input())
    for i in range(0, h):
        for j in range(0, w):
            if list1[i][j] != '1':
                slist.append([j,i])
                n += dfs(list1[i][j])
            #print(list1)
    print(n)
    list1=[]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)
h= 0
w = 0
list1 = []

def dfs(x, y, f):
    list1[y] = list1[y][:x] + '1' + list1[y][x+1:]

    if y - 1 >= 0:
        if list1[y - 1][x] == f:
            dfs(x, y - 1, f)
    if y + 1 < h:
        if list1[y + 1][x] == f:
            dfs(x, y + 1, f)
    if x - 1 >= 0:
        if list1[y][x - 1] == f:
            dfs(x - 1, y, f)
    if x + 1 < w:
        if list1[y][x + 1] == f:
            dfs(x + 1, y, f)
    return

while True:
    h, w = list(map(lambda x: int(x),input().split(" ")))
    if 0 in (h, w):
        break
    n = 0
    for i in range(0, h):
        list1.append(input())
    for i in range(0, h):
        for j in range(0, w):
            if list1[i][j] != '1':
                dfs(j, i, list1[i][j])
                n+=1
    print(n)
    list1=[]

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(20000)


def dfs(x,y,fruit):
  #visited.append((x,y))
  visited[y][x] = 1
  for v in vec:
    nx = x + v[0]
    ny = y + v[1]
    if nx in xrange(w) and ny in xrange(h):
      if visited[ny][nx]==0 and matrix[ny][nx] == fruit:
        dfs(nx,ny,fruit)
  return 0

matrix = []
vec = [[1,0],[-1,0],[0,1],[0,-1]]
visited =[]
h = 0
w = 0

while True:
  h,w = map(int,raw_input().split())
  if h == 0 and w == 0:
    break
#  print h,w
  matrix = []
  visited = []
  ans = 0
  for i in xrange(h):
    s = raw_input().rstrip()
    matrix.append(list(s))
    visited.append([0]*w)
  for i in xrange(h):
    for j in xrange(w):
      #if not (j,i) in visited:
      if visited[i][j] == 0:
        dfs(j,i,matrix[i][j])
        ans+=1
  print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys

sys.setrecursionlimit(20000)

matrix = []
vec = [[1,0],[-1,0],[0,1],[0,-1]]
visited =[]
h = 0
w = 0

def dfs(x,y,fruit):
  #visited.append((x,y))
  visited[y][x] = 1
  for v in vec:
    nx = x + v[0]
    ny = y + v[1]
    if nx in xrange(w) and ny in xrange(h):
      if visited[ny][nx]==0 and matrix[ny][nx] == fruit:
        dfs(nx,ny,fruit)
  return 0


while True:
  h,w = map(int,raw_input().split())
  if h == 0 and w == 0:
    break
#  print h,w
  matrix = []
  visited = []
  ans = 0
  for i in xrange(h):
    s = raw_input().rstrip()
    matrix.append(list(s))
    visited.append([0]*w)
  for i in xrange(h):
    for j in xrange(w):
      #if not (j,i) in visited:
      if visited[i][j] == 0:
        dfs(j,i,matrix[i][j])
        ans+=1
  print ans

Submission status: Accepted

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

def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

def dfs(y,x):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    color[y][x]=1
    for i in xrange(4):
        nextx=x+dx[i]
        nexty=y+dy[i]
        if not check(nexty,nextx):continue
        if g[nexty][nextx]==g[y][x] and color[nexty][nextx]==0:
            dfs(nexty,nextx)
    color[y][x]=2
    return 1
while 1:
    h,w=map(int,raw_input().split())
    if h==w==0:break
    g=[raw_input() for _ in xrange(h)]
    cnt=0
    color=[[0]*w for _ in xrange(h)]
    for i in xrange(h):
        for j in xrange(w):
            if color[i][j]==2:continue
            cnt+=dfs(i,j)
    print(cnt)

Submission status: Accepted

Solution code:
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
field = []
H, W = 0, 0
stack = []

def solver(x, y, symbol):
  global stack, field, H, W
  while True:
    if x < 0 or y < 0 or x >= H or y >= W:
      continue
    for dx, dy in dxy:
      if x+dx < 0 or y+dy < 0 or x+dx >= H or y+dy >= W:
        continue
      if field[x+dx][y+dy] == symbol:
        field[x+dx][y+dy] = '.'
        stack.append([x+dx, y+dy])
    if len(stack) == 0:
      return
    x, y = stack.pop()

while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  field = [list(raw_input()) for i in range(H)]

  ans = 0
  for x in xrange(H):
    for y in xrange(W):
      if field[x][y] != '.':
        solver(x, y, field[x][y])
        ans += 1
  print ans

Submission status: Accepted

Solution code:
import Queue

dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
field = []
H, W = 0, 0
q = Queue.Queue()

def solver(x, y, symbol):
  global q, field, H, W
  while True:
    if x < 0 or y < 0 or x >= H or y >= W:
      continue
    for dx, dy in dxy:
      if x+dx < 0 or y+dy < 0 or x+dx >= H or y+dy >= W:
        continue
      if field[x+dx][y+dy] == symbol:
        field[x+dx][y+dy] = '.'
        q.put([x+dx, y+dy])
    if q.empty():
      return
    x, y = q.get()

while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  field = [list(raw_input()) for i in range(H)]

  ans = 0
  for x in xrange(H):
    for y in xrange(W):
      if field[x][y] != '.':
        solver(x, y, field[x][y])
        ans += 1
  print ans