Existen varios métodos para encontrar la salida de un laberinto, y el mas conocido o mas usado es la regla de "la mano derecha", que consiste en tomar una posición inicial, compruebas si se puede ir a la derecha, si no, abajo, compruebas derecha, etc... siguiendo continuamente la derecha al final encuentras la salida (siempre que no este dentro del laberinto, y este no es el caso).

Eso si, tienes un desafío interesante para el algoritmo, no debería de ser "muy dificil" pero si un poco laborioso, ya que deberás de comprobar cuando se vuelve sobre tus pasos marcar esas casillas como "duplicadas" para encontrar el camino mas corto.

Supongo que se podría crear tuplas de las casillas, y con ellas vectores que te vayan almacenando el camino, siendo el final de cada uno e inicio del siguiente la ultima casilla visitada dos veces (esto al vuelo, sin pensarlo mucho)

Y eso asumiendo una solución, encontrarlas todas puede ser mas "puñetero", pero supongo que a partir de esta idea general se puede empezar a trabajar.

A ver si puedo expresarlo mejor...

Imaginemos una matriz tal que:

00000000010000000
00000000011110000
00000000000010000
00000000000110000
00000000000100000
00000001111111000
00001111000001000
00001000000001100
00000000000000100

Conviene empezar a afrontar este tipo de problemas con ejemplos lo mas simples posibles. Generalmente la solución para un ejemplo sencillo puede aplicarse a uno mas grande. El mismo algoritmo que nos vale para ordenar 3 números nos puede valer para ordenar un millón, solo que a la hora de plantearnos el problema es mucho mas sencillo plantearselos de la forma mas simple posible.

Empecemos con UNA sola posible solución, y a partir de ahi se puede empezar a desarrollar la idea.

¿Por donde empezamos nuestro recorrido?... pues recorremos la primera fila buscando un hueco en la pared, es decir: un uno.

Ya tenemos el inicio, que guardamos. A continuación ¿a donde nos movemos?... pues obviamente miramos los 4 lados, y si solo existe una posibilidad, la seguimos. Si existen dos, empezamos otra ruta "en reserva" y continuamos una de las existentes. De hecho podemos estar seguros de que en un punto dado, nunca tendremos mas de 3 posibilidades, a menos que las 3 que hemos seguido no salgan del laberinto (en cuyo caso toca retroceder a una bifurcación anterior)

Pero vamos, tenemos un punto de inicio, ¿hay solo un camino?... lo seguimos almacenandolo, y marcamos esos pasos. ¿Llegamos a un lugar donde hay 2 posibilidades?, escojemos uno y guardamos el otro para después, así hasta llegar a la última fila, donde obviamente hemos llegado a la salida.

¿Como almacenamos el mapa?... pues parece claro que sería una matriz, de tipo booleano de dos dimensiones, o "0" (pared) o "1" (pasillo), no hay mas misterio.

Para almacenar los diferentes recorridos, dado que no sabemos el numero de pasos necesarios podemos usar un vector o una lista. Ojo, hablo de vectores y listas como clases de C++ en la STD, si no los conoces podemos recurrir a un array clásico que sea lo bastante grande como para contener los movimientos (lo dimensiones a lo grande y a correr, de hecho la longitud mas larga posible sería la total de una fila multiplicado por la mitad de las columnas mas una columna (en realidad un poco menos, pero estoy improvisando sobre la marcha).

Es posible además que existan algoritmos mas eficientes, sería cuestión quizás de buscar un poco.

Tu verás, pero no veo necesario declarar una clase "matriz"... un simple arreglo de booleanos, o de cualquier otra cosa te vale

Por ejemplo un


Y ya tienes una matriz de 10x10, pero como mejor lo veas

Perdón que desvirtúe... pero que edad tenés y a que colegio vas? Si en todos los colegios pedirían cosas como ésta te puedo asegurar que estaría lleno de genios.