def getNeighbours(w, h, coord):
x, y = coord
valid_coords = []
if x > 0:
valid_coords.append((x-1, y))
if x < w - 1:
valid_coords.append((x + 1, y))
if y > 0:
valid_coords.append((x, y - 1))
if y < h - 1:
valid_coords.append((x, y + 1))
return valid_coords
def findMinPossibleAnimals(grid, w, h):
'''
have a 'allowed' character, and a visited coord set. You run bfs such that you can visit a character if they are a allowed character or in the visited coord set. otherwise, they must be a new character which must be saved for the next pass.
'''
allowed_char = grid[0][0]
visited_chars = set()
i = 0
'''
inv: there is atleast one unexplored char in grid equal to allowed_char
'''
while allowed_char != None:
i += 1
next_char = None
visited = { (0, 0) }
toVisit = [(0, 0)]
while len(toVisit) > 0:
node = toVisit.pop()
for neighbour in getNeighbours(w, h, node):
symbol = grid[neighbour[1]][neighbour[0]]
if symbol == '.' or neighbour in visited:
continue
if neighbour in visited_chars or symbol == allowed_char:
visited.add(neighbour)
toVisit.append(neighbour)
else:
next_char = symbol
visited_chars.update(visited)
allowed_char = next_char
return i
def parseGrid(h, w):
grid = []
for row in range(h):
row_inp = [c for c in input()]
grid.append(row_inp)
return grid
def main():
h, w = [int(s) for s in input().split()]
grid = parseGrid(h, w)
print(findMinPossibleAnimals(grid, w, h))
main()
