i have the problem. I have collage project to write a program in C to find shortest way from A to B in maze built by rules:

' '-> avalible way
'#'-> wall
'A'-> start
'B'-> end

Ex of maze n x m; n = 8,m=23

### # # ############## 
# # # #   #   #   #   #
#   #   # # # # # # #  
# #   # #   #   #   # #
 A# # #   #   # # # #  
# # #   #   # #   # # #
#   # #   # #   # #B ##
##      #   ### # # # #

My code looks like it would work but its getting infinite looped idk why. Would someone help me and give some hint how to make it work properly ? Here's my code:

#include <stdlib.h>
#include <stdio.h>

int maze[200][200];

int n,m,counter;
int starti;
int startj;

void shortest(int i,int j,int x)
{

    if(i>=0 && i<n && j>=0 && j<m && maze[i][j] != -1)
    {
        if(maze[i][j] == -999)
        {
            counter = x;
            return;
        }
        maze[i][j] = x;
        //printSol();
        shortest(i 1,j,x 1);
        shortest(i-1,j,x 1);
        shortest(i,j 1,x 1);
        shortest(i,j-1,x 1);
    }


}

void printSol()
{

    int i,j;
    for(i = 0;i<n;i  )
    {
        for(j = 0;j<m;j  )
        {
            printf("-",maze[i][j]);
        }
        printf("\n");

    }
}


int main(){
    int i,j;
    char temp;
    scanf("%d %d",&n,&m);
    fflush(stdin);
    for(i = 0;i<n;i  )
        {
            for(j = 0;j<m;j  )
            {
                scanf("%c",&temp);

                 if(temp == ' ')
                 {
                     maze[i][j] = 0;
                 }
                 if(temp == '#')
                 {
                    maze[i][j] = -1;
                 }
                 if(temp == 'A')
                 {
                     starti = i;
                     startj = j;
                     maze[i][j] = 0;
                 }
                 if(temp == 'B')
                 {
                     maze[i][j] = -999;
                 }
            }
            fflush(stdin);

        }
    printSol();
    shortest(starti,startj,0);
    printf("%d",counter);
    return 0;
}

CodePudding user response：

The problem can solve by a backtracking algorithm. In your code, you have infinity because you can return to the place which have already visited. Check this link there is implementation on C https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/

CodePudding user response：

How to find shortest way in a maze?

You are using a depth-first search. That won't produce a shortest path.^[1] For that, you want a breadth-first search. The first path found will be a shortest path.

While a DFS uses a stack of cells to visit, a BFS uses a queue. It is otherwise identical.

My code [...] [is] getting infinite looped idk why.

Nothing stops the code from going ...-E-W-E-W-E-W-E-W-E-..., so the search enters an infinite loop, crashing when it runs out of stack space.

You need to keep track of which cells have already been visited to avoid revisiting cells that have already been visited.

1. It's technically possible, but it would have to search the entire search space, which can become insanely slow even for small mazes.