Задача: 752. Open the Lock
Сложность: 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.
😎 Решение:
function openLock($deadends, $target) {
function neighbors($node) {
$res = [];
for ($i = 0; $i < 4; $i++) {
$x = intval($node[$i]);
for ($d = -1; $d true];
while (!empty($queue)) {
list($node, $steps) = array_shift($queue);
if ($node === $target) return $steps;
if (isset($dead[$node])) continue;
foreach (neighbors($node) as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue[] = [$neighbor, $steps + 1];
}
}
}
return -1;
}
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
😎 Решение:
function openLock($deadends, $target) {
function neighbors($node) {
$res = [];
for ($i = 0; $i < 4; $i++) {
$x = intval($node[$i]);
for ($d = -1; $d true];
while (!empty($queue)) {
list($node, $steps) = array_shift($queue);
if ($node === $target) return $steps;
if (isset($dead[$node])) continue;
foreach (neighbors($node) as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue[] = [$neighbor, $steps + 1];
}
}
}
return -1;
}
Ставь 👍 и забирай 📚 Базу знаний