Граф Оренье решил съездить в гости к своему другу - графу де Блуа-Шатильону. Не видя причины, почему бы одному благородному дону не посетить с визитом вежливости другого благородного дона, граф Оренье достал карту сопредельных графств и сел составлять маршрут своей поездки. С этим возникла небольшая загвоздка. Дело в том, что внутри каждого графства его хозяин гарантирует своему гостю - другому графу безопасный и бесплатный проезд из любой точки графства в любую другую. Но на границах графств орудуют братцы-разбойники, которые, если поймают богатенького, тотчас требуют с него "въездную визу": кто кошелек, кто коня с каретой, а кто и жизнь ненароком прихватит. Желая минимизировать вероятность встречи с братцами-разбойниками, граф Оренье хочет добраться до графства своего друга де Блуа-Шатильона с минимальным возможным количеством пересечений границ графств. Карта, которую достал граф Оренье, по средневековому обычаю, довольно приблизительная. Вся поверхность земли на ней разбита на единичные квадратики, каждый квадратик принадлежит ровно одному графству и обозначен его буквой. Перемещаться можно только между соседними по стороне квадратиками. Графство Оренье на карте обозначено латинской заглавной буквой O, графство де Блуа-Шатильон обозначено буквой B. Все остальные графства обозначены другими заглавными латинскими буквами, причем каждое графство на этой карте представляет собой связную область. Input format В первой строке содержатся два числа n и m - размеры карты, 1 ≤ n,m ≤ 50. В следующих n строках находятся по m заглавных латинских букв без пробелов - описание карты. Области, занимаемые каждой буквой четырехсвязные. На карте обязательно есть область, обозначенная буквой O и область, обозначенная буквой B. Output format Необходимо вывести минимальное число границ, которые придется пересечь графу Оренье в своем путешествии.

Для решения этой задачи можно использовать алгоритм поиска в ширину (BFS) или поиск в глубину (DFS) с учетом границ между графствами. Основная цель — найти минимальное количество границ, которые необходимо пересечь, чтобы добраться от графства O до графства B.

Алгоритм:

1. Инициализация:

   • Создайте очередь для BFS и структуры данных для хранения посещённых клеток.
   • Поместите начальную позицию графства O в очередь и пометьте её как посещённую. Также создайте переменные для отслеживания текущих пересечений границ.

2. Поиск границ:

   • Извлеките текущую позицию из очереди.
   • Исследуйте соседние клетки (вверх, вниз, влево, вправо).
   • Если соседняя клетка принадлежит тому же графству, что и текущая (например, O), добавьте её в очередь без увеличения счётчика границ.
   • Если соседняя клетка принадлежит другому графству, увеличьте счётчик границ на 1 и поместите её в очередь.

3. Остановка поиска:

   • Если достигнута клетка, принадлежащая графству B, запишите минимальное количество пересечённых границ.

4. Вывод результата.

Пример кода на Python:

from collections import deque

def min_border_crossings(n, m, grid):
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    start = end = None

    # Найдите начальные и конечные позиции
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'O':
                start = (i, j)
            elif grid[i][j] == 'B':
                end = (i, j)

    # BFS
    queue = deque([(start[0], start[1], 0)])  # x, y, borders crossed
    visited = set()
    visited.add((start[0], start[1]))

    while queue:
        x, y, borders_crossed = queue.popleft()

        # Если достигли графства B
        if grid[x][y] == 'B':
            return borders_crossed
        
        current_county = grid[x][y]

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < n and 0 <= ny < m:
                next_county = grid[nx][ny]
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    if next_county == current_county:
                        queue.append((nx, ny, borders_crossed))  # Не пересекаем границу
                    else:
                        queue.append((nx, ny, borders_crossed + 1))  # Пересекаем границу

    return -1  # На всякий случай, если путь не найден (хотя по условию это невозможно)

# Чтение входных данных
n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]

# Вывод результата
result = min_border_crossings(n, m, grid)
print(result)

Объяснение кода:

• Определяются направления движения.
• Затем осуществляется поиск стартовой и конечной позиции.
• Используется очередь для BFS, где для каждой клетки хранятся координаты и количество пересечённых границ.
• Алгоритм проверяет соседние клетки, добавляя их в очередь с учётом принадлежности к графству. Если найденное графство B, выводится количество пересечённых границ.

Заключение:

Этот метод позволяет эффективно найти минимальное количество границ, которые необходимо пересечь при переходе от графства O к графству B. Попробуйте реализовать и протестировать его на ваших примерах!