Ключи в цифровом лабиринте

1. Идея

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

Например, в одну и ту же клетку можно прийти:

• без ключей;
• с ключом a;
• с ключами a и c.

Это разные ситуации, потому что из них можно пойти в разные двери.

Поэтому состояние в BFS должно состоять из трёх частей:

• координаты клетки x, y;
• набор собранных ключей;
• расстояние от старта.

Набор ключей удобно хранить в битовой маске. Так как типов ключей не больше 6, достаточно числа от 0 до 63.

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

Наблюдение 1. Нужно хранить посещённость не только по клетке

Если отметить клетку как посещённую только по координатам, можно потерять правильный путь.

Пример идеи:

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

Значит, посещённость должна быть вида visited[x][y][mask].

Наблюдение 2. Ключи удобно кодировать битами

Пусть:

• ключ a — это бит 0,
• ключ b — бит 1,
• ...
• ключ f — бит 5.

Тогда:

• получить ключ c можно так: mask |= (1 << 2);
• проверить, есть ли ключ для двери C: (mask & (1 << 2)) != 0.

Наблюдение 3. BFS даёт кратчайший путь

Каждый ход имеет одинаковую стоимость: 1. Значит, обычный BFS по состояниям найдёт минимальное число ходов до первой встречи с клеткой T.

Наблюдение 4. Символ цели отделён от символов дверей

Целевая клетка обозначается символом T, поэтому она не конфликтует с дверями A...F. Войти в T можно как в обычную проходимую клетку; ограничения по ключам применяются только к дверям.

3. Алгоритм

1. Считать лабиринт.
2. Найти стартовую клетку S.
3. Создать массив посещённости visited[n][m][64], где:
   • первые две координаты — позиция;
   • третья — маска ключей.
4. Запустить BFS из состояния:
   • позиция S,
   • маска 0,
   • расстояние 0.
5. Пока очередь не пуста:
   • достать очередное состояние;
   • если текущая клетка — T, вывести расстояние и завершить программу;
   • перебрать 4 соседние клетки;
   • пропустить выход за границы;
   • пропустить #;
   • если клетка содержит символ от A до F, проверить наличие соответствующего ключа;
   • если клетка содержит ключ от a до f, добавить его в маску;
   • если состояние с новой позицией и новой маской ещё не посещалось, добавить его в очередь.
6. Если BFS закончился и цель не найдена, вывести -1.

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

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

1. BFS перебирает все достижимые состояния

Состояние задаётся тройкой:

• текущая клетка,
• набор ключей,
• длина пути до неё.

Из каждого состояния мы перебираем все допустимые переходы в соседние клетки:

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

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

2. Одно и то же состояние не обрабатывается дважды

Мы используем visited[x][y][mask]. Если состояние уже было посещено, повторно его в очередь не добавляем.

Это важно:

• алгоритм не зациклится;
• время работы останется разумным.

3. Первый найденный путь до T — кратчайший

BFS работает слоями:

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

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

4. Почему нужно различать разные маски в одной клетке

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

Значит, поиск по состояниям (x, y, mask) необходим и достаточен для корректного решения.

5. Сложность

Пусть:

• n * m — число клеток,
• масок ключей 64.

Тогда число возможных состояний не больше n * m * 64.

Каждое состояние обрабатывается не более одного раза, и из него рассматривается до 4 переходов.

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

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

При ограничении n * m <= 40000 это укладывается в разумные пределы.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#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];
    }

    int sx = -1, sy = -1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }

    vector<vector<vector<bool>>> visited(
        n, vector<vector<bool>>(m, vector<bool>(64, false))
    );

    queue<tuple<int, int, int, int>> q;
    q.push({sx, sy, 0, 0});
    visited[sx][sy][0] = true;

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

    while (!q.empty()) {
        auto [x, y, mask, dist] = q.front();
        q.pop();

        if (grid[x][y] == 'T') {
            cout << dist << '
';
            return 0;
        }

        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;
            }

            char c = grid[nx][ny];
            if (c == '#') {
                continue;
            }

            if (c >= 'A' && c <= 'F') {
                int need = c - 'A';
                if ((mask & (1 << need)) == 0) {
                    continue;
                }
            }

            int nmask = mask;
            if (c >= 'a' && c <= 'f') {
                nmask |= (1 << (c - 'a'));
            }

            if (!visited[nx][ny][nmask]) {
                visited[nx][ny][nmask] = true;
                q.push({nx, ny, nmask, dist + 1});
            }
        }
    }

    cout << -1 << '
';
    return 0;
}

7. Код на Python 3

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

sx = sy = -1
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'S':
            sx, sy = i, j

visited = [[[False] * 64 for _ in range(m)] for _ in range(n)]
visited[sx][sy][0] = True

queue = [(sx, sy, 0, 0)]
head = 0

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

while head < len(queue):
    x, y, mask, dist = queue[head]
    head += 1

    if grid[x][y] == 'T':
        print(dist)
        break

    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

        c = grid[nx][ny]
        if c == '#':
            continue

        if 'A' <= c <= 'F':
            need = ord(c) - ord('A')
            if (mask & (1 << need)) == 0:
                continue

        nmask = mask
        if 'a' <= c <= 'f':
            nmask |= 1 << (ord(c) - ord('a'))

        if not visited[nx][ny][nmask]:
            visited[nx][ny][nmask] = True
            queue.append((nx, ny, nmask, dist + 1))
else:
    print(-1)