Разбор задачи «Тревога в железной крепости»

1. Идея

Нужно смоделировать распространение тревоги по клетчатой сетке.

Есть три типа залов:

• 0 — пустой, на него тревога не влияет;
• 1 — спокойный гарнизон, который нужно охватить тревогой;
• 2 — тревога уже поднята.

Каждую минуту тревога переходит из всех текущих тревожных залов в соседние по стороне залы со значением 1.

Это очень похоже на распространение волны. Для таких процессов естественно использовать поиск в ширину — BFS.

Причём запускать его нужно сразу из всех клеток с 2, потому что тревога начинается одновременно из всех уже охваченных залов.

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

Наблюдение 1

Если в крепости вообще нет залов со спокойным гарнизоном, то ответ сразу 0.

Ничего распространять не нужно.

Наблюдение 2

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

Тогда ответ -1.

Наблюдение 3

Обычный BFS по слоям идеально соответствует минутам:

• все клетки, которые уже в очереди, распространяют тревогу в текущую минуту;
• новые клетки попадают в очередь и будут распространять тревогу уже в следующую минуту.

Поэтому если обрабатывать очередь по уровням, то число уровней и будет числом минут.

Наблюдение 4

Чтобы не заражать одну и ту же клетку много раз, сразу после добавления в очередь нужно менять её значение с 1 на 2.

3. Алгоритм

1. Считываем m и n, затем всю сетку.
2. Создаём очередь.
3. Все клетки со значением 2 сразу кладём в очередь.
4. Подсчитываем количество спокойных залов fresh — это число клеток со значением 1.
5. Если fresh == 0, выводим 0.
6. Иначе запускаем BFS:
   • пока очередь не пуста и ещё остались спокойные залы:
     • запоминаем текущий размер очереди — это все клетки текущей минуты;
     • увеличиваем счётчик минут;
     • обрабатываем ровно эти клетки;
     • для каждой проверяем 4 соседей;
     • если сосед находится в пределах сетки и равен 1, то:
       • меняем его на 2;
       • уменьшаем fresh;
       • добавляем в очередь.
7. После завершения:
   • если fresh > 0, выводим -1;
   • иначе выводим число минут.

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

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

1. Все начальные тревожные залы стартуют одновременно

Мы помещаем в очередь все клетки со значением 2 ещё до начала обхода. Значит, BFS идёт сразу из всех источников тревоги.

2. Один слой BFS соответствует одной минуте

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

Значит, после первой итерации тревога распространится на расстояние 1, после второй — на расстояние 2 и так далее.

3. Каждая клетка заражается в минимально возможный момент

BFS всегда впервые достигает вершину кратчайшим путём по числу шагов. Здесь шаг — это переход в соседний по стороне зал за одну минуту.

Следовательно, если спокойный зал достижим, то алгоритм переведёт его в состояние 2 ровно в минимальное возможное число минут.

4. Если после обхода остались клетки 1, то они недостижимы

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

Следовательно, алгоритм корректно выводит:

• минимальное число минут, если все достижимы;
• -1, если часть гарнизона недостижима.

5. Сложность

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

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

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

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

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) {
        return 0;
    }

    vector<vector<int>> grid(n, vector<int>(m));
    queue<pair<int, int>> q;
    int fresh = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 2) {
                q.push({i, j});
            } else if (grid[i][j] == 1) {
                ++fresh;
            }
        }
    }

    if (fresh == 0) {
        cout << 0 << '\n';
        return 0;
    }

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

    int minutes = 0;

    while (!q.empty() && fresh > 0) {
        int sz = (int)q.size();
        ++minutes;

        for (int k = 0; k < sz; ++k) {
            auto [x, y] = q.front();
            q.pop();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (grid[nx][ny] != 1) continue;

                grid[nx][ny] = 2;
                --fresh;
                q.push({nx, ny});
            }
        }
    }

    if (fresh > 0) {
        cout << -1 << '\n';
    } else {
        cout << minutes << '\n';
    }

    return 0;
}

7. Код на Python 3

import sys
from collections import deque

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    grid = [[0] * m for _ in range(n)]
    q = deque()
    fresh = 0

    for i in range(n):
        for j in range(m):
            grid[i][j] = int(next(it))
            if grid[i][j] == 2:
                q.append((i, j))
            elif grid[i][j] == 1:
                fresh += 1

    if fresh == 0:
        print(0)
        return

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

    while q and fresh > 0:
        for _ in range(len(q)):
            x, y = q.popleft()
            for dx, dy in directions:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh -= 1
                    q.append((nx, ny))
        minutes += 1

    print(-1 if fresh > 0 else minutes)

if __name__ == "__main__":
    main()