752. Open the Lock
Перед вами замок с 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
C# решение
сопоставлено/оригинал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;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int OpenLock(vector<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.size() > 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.push_back(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.push_back(new string(nodeArray));
nodeArray[i] = (char)(x + '0');
}
}
return res;
}
}Java решение
сопоставлено/оригиналimport java.util.*;
public class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
Queue<String> queue = new LinkedList<>();
queue.offer("0000");
Set<String> visited = new HashSet<>();
visited.add("0000");
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String node = queue.poll();
if (node.equals(target)) {
return steps;
}
if (dead.contains(node)) {
continue;
}
for (String neighbor : neighbors(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
steps++;
}
return -1;
}
private List<String> neighbors(String node) {
List<String> res = new ArrayList<>();
char[] nodeArray = node.toCharArray();
for (int i = 0; i < 4; i++) {
char original = nodeArray[i];
nodeArray[i] = original == '9' ? '0' : (char) (original + 1);
res.add(new String(nodeArray));
nodeArray[i] = original == '0' ? '9' : (char) (original - 1);
res.add(new String(nodeArray));
nodeArray[i] = original;
}
return res;
}
}JavaScript решение
сопоставлено/оригиналvar openLock = function(deadends, target) {
function neighbors(node) {
const res = [];
for (let i = 0; i < 4; i++) {
const x = parseInt(node[i]);
for (const d of [-1, 1]) {
const y = (x + d + 10) % 10;
res.push(node.slice(0, i) + y + node.slice(i + 1));
}
}
return res;
}
const dead = new Set(deadends);
const queue = [['0000', 0]];
const visited = new Set('0000');
while (queue.length) {
const [node, steps] = queue.shift();
if (node === target) return steps;
if (dead.has(node)) continue;
for (const neighbor of neighbors(node)) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, steps + 1]);
}
}
}
return -1;
};Python решение
сопоставлено/оригиналfrom collections import deque
def openLock(deadends, target):
def neighbors(node):
for i in range(4):
x = int(node[i])
for d in (-1, 1):
y = (x + d) % 10
yield node[:i] + str(y) + node[i+1:]
dead = set(deadends)
queue = deque([('0000', 0)])
visited = {'0000'}
while queue:
node, steps = queue.popleft()
if node == target:
return steps
if node in dead:
continue
for neighbor in neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return -1Go решение
сопоставлено/оригиналpackage main
import (
"fmt"
)
func openLock(deadends []string, target string) int {
neighbors := func(node string) []string {
res := []string{}
for i := 0; i < 4; i++ {
x := node[i] - '0'
for _, d := range []int{-1, 1} {
y := (x + byte(d) + 10) % 10
res = append(res, node[:i]+string(y+'0')+node[i+1:])
}
}
return res
}
dead := make(map[string]bool)
for _, d := range deadends {
dead[d] = true
}
queue := []string{"0000"}
steps := 0
visited := make(map[string]bool)
visited["0000"] = true
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
if node == target {
return steps
}
if dead[node] {
continue
}
for _, neighbor := range neighbors(node) {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
steps++
}
return -1
}Algorithm
Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.
Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.
Если очередь пуста и целевое состояние не найдено, верните -1.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.