¿Coincide con el algoritmo de búsqueda de pares?

Question

Encontré un interesante juego de parejas en http://xepthu.uhm.vn.La regla es simple: debes encontrar y conectar dos Pokémon idénticos, pero el camino entre ellos no está bloqueado y la dirección no se puede cambiar 3 veces.Veamos un ejemplo:

He pensado mucho en el algoritmo para verificar si la ruta entre los 2 Pokémon seleccionados es válida, pero como soy un novato, no puedo encontrar ninguna solución.¿Puedes sugerirme uno en C#?

Answer 1

Esto es básicamente un problema para encontrar camino desde teoría de grafos . Los campos de la rejilla son los nodos, y todos los campos adyacentes están conectados por un borde.

hallazgo Path es un problema bien conocido, y hay muchos algoritmos que resuelvan esto. Debido a que su gráfica es bastante pequeño, la mejor solución es probablemente sólo un algoritmo de fuerza bruta. Un algoritmo hallazgo ruta popular es algoritmo de Dijkstra .

---

La fuerza bruta: Inicio en algún pokemon y explorar todas las vías posibles para ver si uno conduce a un pokemon idénticos. Puede detener la exploración de una manera si el camino está bloqueado o tiene más de 2 vueltas.

Se va a necesitar algo que apunta "puntero" a un campo en la cuadrícula. El puntero se puede mover hacia la izquierda, derecha, arriba o abajo, a condición de que el campo en esa dirección no está bloqueado. Mover el puntero a un campo adyacente. Recuerda de dónde viene y cuántas vueltas que ha realizado. Repita este procedimiento hasta que haya alcanzado su destino. Dar marcha atrás si el número de vueltas alcanza 3. Asegúrese de que no se quede en círculos.

Answer 2

Eche un vistazo a los gráficos planos.Tendrás que introducir una segunda condición:no se pueden recorrer más de cuatro nodos (nodo inicial - primer cambio de dirección - segundo cambio de dirección - nodo final).