Trovare il percorso più corto per le pedine sincronizzate in un labirinto

Question

Ho cercato di avvolgere la testa attorno a questo problema e non riesco proprio a prenderlo.

• Abbiamo un $ a tempi b $ matrice in cui ogni cella corrisponde a uno spazio vuoto, indicato con un punto o un muro, indicato con $ X $.

• Ci sono due pedine in diverse posizioni all'interno del labirinto, i loro movimenti sono sincronizzati e devono lasciare il labirinto (ha più uscite) nella stessa mossa.

• Se uno si muove e l'altro è contro un muro, è una mossa valida e l'altra rimane in posizione.

• L'obiettivo è scrivere un algoritmo che trova le mosse più basse possibili per far uscire entrambi dal labirinto allo stesso tempo, della complessità del tempo $ mathcal o (a^2 b^2) $.

Ho ricevuto alcuni consigli per usare BFS per questo problema, ma non capisco come si occuperà di tutto il backtracking che deve essere fatto. Ho incluso due visualizzazioni con i percorsi corretti etichettati per aiutare a spiegare il problema.

---

Esempio 1: Posizioni di partenza del pegno mostrate come quadrati blu

---

Esempio 2: Posizione di partenza del pegno mostrata come quadrato blu e quadrato