Задача D
Глупая ситуация

Разбор решения

Условие

• Палец инженера застрял в цифре d дискового телефона
• Есть m пар номеров, которые общаются между собой — звонить можно только по таким парам
• Если номер врача набрать нельзя, Щукин звонит знакомому, тот передаёт просьбу по цепочке, а врач в конце перезванивает Щукину
• Найти минимальное число звонков, или −1, если связаться нельзя

Какие цифры можно набрать

Цифры на диске идут от стопора так:

Цифра x доступна, если x ≠ 0 и x ≤ d.

Если d = 0, доступно всё: 0 — самая дальняя цифра.

Переходим к графу

Вершины — номера, рёбра — пары «общаются». Пример, d = 9:

Жёлтый — врач. Набрать можно только номера без нуля.

BFS от врача

Сколько звонков

Выгоднее всего ближайший к врачу набираемый v — BFS находит его первым.

В примере: v = 1987629, 1 + 2 + 1 = 4

Когда ответ −1

Код

bool canDial(const string& number) {
    if (d == 0) return true;
    for (char c : number)
        if (c == '0' || c - '0' > d) return false;
    return true;
}

map<string, vector<string>> graph;   // graph[a].push_back(b) и наоборот
if (canDial(doctor)) { cout << 1; return 0; }

set<string> visited = {doctor};
queue<pair<string, int>> q;          // номер и расстояние
q.push({doctor, 0});
int dist = -1;
while (!q.empty()) {
    auto [v, k] = q.front(); q.pop();
    if (canDial(v)) { dist = k; break; }           // нашли - стоп
    for (const string& to : graph[v])
        if (!visited.count(to)) { visited.insert(to); q.push({to, k + 1}); }
}

if (dist == -1) cout << -1;
else cout << dist + 2;

Итог

• Цифра доступна, если она не 0 и не больше d (при d = 0 — все)
• Номера — вершины, пары «общаются» — рёбра
• BFS от врача до первого набираемого номера, ответ — dist + 2 или −1

BFS по шагам