1. Идея

Нужно для каждой клетки узнать расстояние до ближайшего маяка B, двигаясь только по проходимым клеткам и только по четырём направлениям.

Если бы маяк был один, можно было бы запустить обычный BFS из него и получить расстояния до всех достижимых клеток.

Но маяков может быть несколько. Запускать BFS отдельно от каждого маяка слишком долго. Вместо этого используется multi-source BFS: кладём в очередь сразу все клетки с маяками и считаем, что расстояние до них равно 0. После этого BFS сам распространит минимальные расстояния по карте.

Это и есть естественный способ найти расстояние до ближайшего из нескольких источников в невзвешенном графе.

2. Наблюдения

1. Карту удобно рассматривать как граф:

   • каждая не заблокированная клетка — вершина;
   • между соседними по стороне проходимыми клетками есть ребро;
   • все рёбра имеют одинаковый вес 1.

2. В графе с одинаковыми весами кратчайшие расстояния находятся BFS.

3. Если стартовать BFS сразу из всех маяков:

   • клетка, до которой первым дошла волна BFS, получает минимальное возможное расстояние;
   • это расстояние будет именно до ближайшего маяка.

4. Препятствия # вообще не участвуют в обходе:

   • в них нельзя заходить;
   • в ответе для них всегда -1.

5. Если какая-то проходимая клетка после BFS так и осталась с расстоянием -1, значит до неё нельзя добраться ни от одного маяка из-за стен.

3. Алгоритм

1. Считываем n, m и саму карту.
2. Создаём массив dist размера n x m, заполняем его значениями -1.
3. Создаём очередь BFS.
4. Проходим по всем клеткам:
   • если в клетке стоит маяк B, то:
     • записываем dist[i][j] = 0;
     • добавляем эту клетку в очередь.
5. Пока очередь не пуста:
   • извлекаем клетку (x, y);
   • пробуем перейти в 4 соседние клетки;
   • если сосед:
     • находится внутри карты,
     • не является #,
     • ещё не посещён (dist[nx][ny] == -1), то:
     • записываем dist[nx][ny] = dist[x][y] + 1;
     • добавляем его в очередь.
6. Выводим ответ:
   • если клетка #, печатаем -1;
   • иначе печатаем dist[i][j].

4. Почему это работает

Докажем, что алгоритм действительно находит расстояние до ближайшего маяка для каждой клетки.

1. Почему BFS вообще находит кратчайшие расстояния

В BFS очередь работает по слоям:

• сначала обрабатываются все клетки на расстоянии 0,
• потом все клетки на расстоянии 1,
• потом на расстоянии 2 и так далее.

Значит, когда клетка впервые получает значение dist, это минимальное количество шагов, за которое до неё можно добраться от стартовых вершин.

2. Почему можно стартовать сразу из всех маяков

Мы кладём в очередь все клетки с B с расстоянием 0.

Это эквивалентно запуску BFS одновременно от всех маяков. Волны обхода идут навстречу друг другу, и каждая клетка будет впервые достигнута от того маяка, до которого путь короче всего.

Если бы существовал более короткий путь до какого-то маяка, BFS достиг бы клетку раньше и записал бы меньшее расстояние. Значит, первое записанное значение уже минимально.

3. Почему препятствия обрабатываются правильно

Клетки # мы не добавляем в очередь и не переходим через них. Поэтому BFS рассматривает только допустимые пути по проходимым клеткам.

Следовательно:

• для препятствий ответ должен быть -1;
• для недостижимых проходимых клеток расстояние так и останется -1.

Значит, итоговый вывод полностью соответствует условию.

5. Сложность

Пусть всего n * m клеток.

• Каждая клетка добавляется в очередь не более одного раза.
• Для каждой клетки проверяются 4 соседа.

Итоговая сложность:

• по времени: O(n * m)
• по памяти: O(n * m)

Это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'B') {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int x = cur.first;
        int y = cur.second;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }
            if (grid[nx][ny] == '#') {
                continue;
            }
            if (dist[nx][ny] != -1) {
                continue;
            }

            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j > 0) {
                cout << ' ';
            }
            if (grid[i][j] == '#') {
                cout << -1;
            } else {
                cout << dist[i][j];
            }
        }
        cout << '\n';
    }

    return 0;
}

7. Код на Python 3

from collections import deque

n, m = map(int, input().split())
grid = [input() for _ in range(n)]

dist = [[-1] * m for _ in range(n)]
q = deque()

for i in range(n):
    for j in range(m):
        if grid[i][j] == 'B':
            dist[i][j] = 0
            q.append((i, j))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while q:
    x, y = q.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if grid[nx][ny] == '#':
            continue
        if dist[nx][ny] != -1:
            continue
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx, ny))

for i in range(n):
    row = []
    for j in range(m):
        if grid[i][j] == '#':
            row.append("-1")
        else:
            row.append(str(dist[i][j]))
    print(" ".join(row))