Buenos días a todos, estoy resolviendo un problema en la siguiente web:
codingame.com (totalmente recomendada si no la conociais). El caso es que para resolverlo he creado una clase como esta:
class Node {
int id;
final List<Node> connectedNodes = new List<Nodes>();
Node(this.id);
void connectNodes(Node otherNode) {
if (otherNode == null) return;
connectedNodes.add(otherNode);
otherNode.connectedNodes.add(this);
}
void removeLinks(Node otherNode) {
if (otherNode == null) return;
connectedNodes.removeWhere((node) => node == otherNode);
otherNode.connectedNodes.removeWhere((node) => node == this);
}
}
Y en el main tengo la siguiente lista:
List<Node> nodes = new List<Node>(size);
Ahora bien, necesito una función para encontrar la distancia minima entre dos nodos. Tras devanarme los sesos durante un buen rato, he escrito la siguiente función que (sorpresa, sorpresa), no funciona.
int findDistance(int id1, int id2) {
int count = 0;
if (id1 == id2) return 0;
Node node1 = nodes[id1];
Node node2 = nodes[id2];
List<int> idsExpanded = new List<int>();
List<int> distances = new List<int>();
void expand(Node n1) {
count++;
for (var subNode in n1.connectedNodes) {
if (subNode.id == id2) distances.add(count);
if (!idsExpanded.contains(subNode.id)) {
idsExpanded.add(subNode.id);
expand(subNode);
}
}
count--;
}
expand(node1);
// Las ordena de menor a mayor
distances.sort();
return distances.first;
}
He buscado información sobre búsqueda en árboles y grafos por ahí, pero debido a que mis conocimientos de algoritmos son muy limitados (no soy universitario ni nada de eso, he aprendido por mi cuenta) no suelo entender las páginas que encuentro.
Agradecería si alguien me pudiese explicar el método que debería usar o cual es la manera optima de diseñar esta función.
El maravilloso lenguaje que estoy usando es Dart, una especie de mezcla entre javascript y Java, para que nadie se asuste
Un saludo y gracias de antemano.
PD: El problema es el Skynet Finale - Level 2, de los difíciles, por si alguien ya conocía la página
Mostrar Mensajes
En fin, la informática es así 