Modifica nel problema del tour del cavaliere

0

Quindi ho un problema con il tour di un cavaliere modificato. Il problema è il seguente, c'è un algoritmo che può darti il percorso (se possibile il più breve) da (1,1) a (n, m) in una scacchiera del pezzo del cavaliere? E anche se alcuni blocchi sono bloccati Per esempio. Ho una scacchiera 3x5 e i blocchi (2,3) e (2,5) sono bloccati. C'è un possibile percorso perché il mio cavaliere passi da (1,1) a (3,5) senza che il mio cavaliere passi i blocchi negati (può passare attraverso di loro ma non rimanere su di essi)

    
posta Maverick98 18.11.2017 - 13:37
fonte

1 risposta

4

Certo. La tua scacchiera (o le celle non bloccate) formano un grafico , dove ogni cella è un vertice del grafico, e ogni movimento di cavaliere consentito da un nodo all'altro definisce un bordo. Il percorso più breve per il cavaliere può quindi essere trovato da una semplice ricerca in ampiezza .

Per implementare questo, utilizzare un array intero 2D per rappresentare la griglia. Basta assegnare il valore zero alla cella iniziale, quindi determinare tutte le celle raggiungibili con una mossa da lì e contrassegnarle con 1, quindi eseguire il ciclo attraverso tutte le 1 celle, determinare tutte le celle raggiungibili con una mossa da quelle non visitate prima e contrassegnarle con "2", e così via, fino a raggiungere il nodo finale (n, m). Avrai bisogno di alcuni valori speciali che indicano celle e celle bloccate non visitate fino ad ora.

Per ottenere il percorso finale dall'array 2D, avviare una ricerca su (n, m). Diciamo che questa cella ha il numero k, quindi cerca un vicino di trasloco cavalieri con valore k-1, quindi da lì per un vicino con valore k-2, e così via. Questo produrrà il percorso che stavi cercando in ordine inverso.

    
risposta data 18.11.2017 - 13:51
fonte

Leggi altre domande sui tag