Gracias por A2A, este es un acertijo bastante interesante.
Y si no me equivoco, este es de codeVita 2014
Puedes hacerlo con fuerza bruta y un poco de ayuda con trucos.
Primero, entendamos nuestro escenario 
‘O’ son celdas abiertas ‘X’ son paredes y digamos ‘A’ son ratas.
- ¿Cómo se utilizan las estructuras de datos en las industrias?
- ¿Necesito estudiar la teoría de estructuras de datos y algoritmos antes de resolver las preguntas en InterviewBit?
- ¿Cuáles son las aplicaciones de la lista de enlaces simple, doble, circular y de encabezado en la estructura de datos?
- ¿Cuáles son las piezas más llamativas del arte algorítmico?
- ¿Cómo debería abordar la mejora de mi algoritmo, si mi conjunto de pruebas arroja malos resultados?
Tienes que usar el método de seguimiento.
Paso 1: – Comienza con cualquier rata al azar (o con la que encuentres primero)
Paso 2: – Mira a las celdas derecha, izquierda, superior e inferior de esta rata (esto creará 4 ramas diferentes)
Paso 3: tome todas estas 4 ramas 1 por 1 (supongo que conoce el método de seguimiento)
Paso 4: mientras tanto, realice un seguimiento de todos los nodos visitados en una matriz
Paso 5: – Cada vez que visites una nueva celda habrá 3 opciones
Paso 5.1: si la celda nueva tiene X, descarte toda la rama y muévase a la siguiente rama
Paso 5.2: – si la nueva celda tiene A marca a la rata como “alcanzada” (o meta alcanzada o lo que quieras)
Paso 5.3: – si la nueva celda tiene la marca O, continúe en la rama y llame a la misma función recursivamente para t 
Él esta nueva posición.
Recuerde que cada vez que se mude a una nueva celda, asegúrese de que esta nueva celda no haya sido visitada antes.
Repita los pasos anteriores para todas las ratas. Consejo: – cada vez que una Rata llegue a otra Rata marca a ambas ratas como completadas.
Retroceder será un buen enfoque para esto.
Pruébalo, espero que puedas lograrlo.
Espero eso ayude.
