Anyone can help me, I need to develop a recursive function that tests all the paths and returns the shortest.
Give a labyrinth in the form of a binary rectangular matrix (M, N), find the shortest path in the maze of an origin (xini, yini) to a given destination (xfim, yfim), where xini, yini, xfim, yfim are cells of the matrix MxN. The path must be built with cells having the value 1.
To find the shortest path in the labyrinth, you have to search all the possible paths in the maze, from beginning to end. The search starts from the origin in the informed cell of the matrix and explores the four possible directions, recursively checking whether they lead to the destination or not. The minimum path is updated if the target cell is found. If a path does not lead to the destination or if all routes have already been crawled from the current cell, take a step back. To make sure that the path is simple and contains no cycles, record the path of the cells involved in the array before exploring another cell. If the cell has already been visited, it is ignored (not browsed again).
Tip: To store the traversed paths, use an auxiliary matrix of the same size as the maze matrix to indicate whether the cell has already been visited (1) or not (0). If a path does not lead to the solution, the auxiliary matrix cell is deselected as visited.
My code up here:
int Labirinto(int m, int n, int mat()(n), int percorrido()(n), int xPos, int yPos, int xFin, int yFin, int *Atual)
if(*Atual == 0)
menorCaminho = m*n;
*Atual = *Atual + 1;
percorrido(xPos)(yPos) = 1;
In the code I wrote, the smallerPath variable does not get the contents of the current path, even though entering this if.
if(xPos == xFin && yPos == yFin)
//Testa se um caminho mais curto foi encontrado
if(menorCaminho > *Atual)
menorCaminho = *Atual;
*Atual = *Atual - 1;
I also have problems here, as long as conditions are met, the first conditional is never executed.
else if((mat(xPos+1)(yPos) == 1) && (xPos+1=0 && percorrido(xPos-1)(yPos) == 0)
Labirinto(m, n, mat, percorrido, xPos-1, yPos, xFin, yFin, &*Atual);
percorrido(xPos-1)(yPos) = 0;
else if(mat(xPos)(yPos-1) == 1 && yPos-1>=0 && percorrido(xPos)(yPos-1) == 0)
Labirinto(m, n, mat, percorrido, xPos, yPos-1, xFin, yFin, &*Atual);
percorrido(xPos)(yPos-1) = 0;
*Atual = *Atual - 1;
//INÍCIO DO FUNÇÃO PRINCIPAL
int m, n, xInicial, yInicial, xFinal, yFinal, mat(100)(100), percorrido(100)(100), i, j, caminhoAtual = 0;