Abbinare l'algoritmo di ricerca coppie?

Question

Ho trovato un interessante gioco di corrispondenza coppie a http://xepthu.uhm.vn . La regola è semplice, dovete trovare e collegare due pokemon identici ma il percorso tra di loro non è bloccata e la direzione non non può essere modificato 3 volte. Vediamo un esempio:

Non ho pensare molto su l'algoritmo per verificare se il percorso tra ogni 2 Pokémon selezionato è valido, ma perché io sono un novizio, quindi non riesco a trovare alcuna soluzione. Mi potete suggerire uno in C #?

Answer 1

Questo è fondamentalmente un percorso trovando problema da teoria dei grafi . I campi nella griglia sono i nodi, e tutti i campi adiacenti sono collegati da un bordo.

Percorso trovare è un problema ben noto, e ci sono molti algoritmi che risolvono questo. Dal momento che il grafico è abbastanza piccola, la soluzione migliore è probabilmente solo un algoritmo di forza bruta. Un algoritmo di percorso popolare trovare è di Dijkstra algoritmo .

---

La forza bruta: Inizia a un certo pokemon ed esplorare tutti i modi possibili per vedere se uno porta ad un pokemon identico. Si può smettere di esplorare un modo se la strada è bloccata o ha più di 2 giri.

Avrete bisogno di un po 'di "puntatore" che punta a un campo nella griglia. Il puntatore può spostarsi a sinistra, destra, in alto o in basso, a condizione che il campo in quella direzione non sia bloccato. Spostare il puntatore su un campo adiacente. Ricorda da dove vieni e quanti giri hai fatto. Ripetere questa operazione fino a quando hai raggiunto la destinazione. Tornate indietro, se il numero di giri raggiunge 3. Assicurarsi che non si esegue nei circoli.

Answer 2

Date un'occhiata a grafi planari. Si dovrà introdurre una seconda condizione:. Non più di quattro nodi possono essere attraversati (inizio nodo - primo cambio di direzione - secondo cambio di direzione - nodo finale)