Сложность: medium
Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.
Пример:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
👨💻 Алгоритм:
1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.
2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.
3⃣Если очередь пуста и целевое состояние не найдено, верните -1.
😎 Решение:
public class Solution {
public int OpenLock(string[] deadends, string target) {
var dead = new HashSet<string>(deadends);
var queue = new Queue<(string, int)>();
queue.Enqueue(("0000", 0));
var visited = new HashSet<string> { "0000" };
while (queue.Count > 0) {
var (node, steps) = queue.Dequeue();
if (node == target) return steps;
if (dead.Contains(node)) continue;
foreach (var neighbor in Neighbors(node)) {
if (!visited.Contains(neighbor)) {
visited.Add(neighbor);
queue.Enqueue((neighbor, steps + 1));
}
}
}
return -1;
}
private IEnumerable<string> Neighbors(string node) {
var res = new List<string>();
var nodeArray = node.ToCharArray();
for (int i = 0; i < 4; i++) {
var x = nodeArray[i] - '0';
for (int d = -1; d <= 1; d += 2) {
var y = (x + d + 10) % 10;
nodeArray[i] = (char)(y + '0');
res.Add(new string(nodeArray));
nodeArray[i] = (char)(x + '0');
}
}
return res;
}
}Ставь 👍 и забирай 📚 Базу знаний