Finding Shortest Path In A Labyrinth with C

Question

I want to write a code to find a shortest path in the labyrinth. I wrote this;

#include <stdio.h>

void change (void);
void print(void);

int labirent[13][13] = {
            {1,1,1,1,1,1,1,1,1,1,1,1,1},
            {1,2,0,1,0,0,0,0,0,0,0,0,1},
            {1,0,0,1,0,0,1,0,1,1,1,1,1},
            {1,0,0,1,0,0,1,0,0,0,0,0,1},
            {1,0,0,0,0,0,1,0,0,0,0,0,1},
            {1,0,0,0,0,1,1,1,1,0,0,0,1},
            {1,0,1,1,1,1,1,0,0,0,0,0,1},
            {1,0,0,0,0,1,0,0,0,1,1,1,1},
            {1,0,0,0,0,1,0,0,0,0,0,0,1},
            {1,1,1,1,0,1,0,0,1,1,0,0,1},
            {1,0,0,0,0,1,0,0,1,0,0,1,1},
            {1,0,0,0,0,0,0,0,1,0,0,3,1},
            {1,1,1,1,1,1,1,1,1,1,1,1,1}
    };//defining labyrinth - walls are (1), starting point is (2), null points are (0), end point is (3)

int i = 3;
int a = 0;

int x=1, y=1;//current positions

int main(){

    change();

    print();

 return 0;   
}

void change(){


        if(labirent[x+1][y]==0){
            labirent[x+1][y]=i;
            x = x + 1;
            change();
        }else if(labirent[x][y+1]==0){
            labirent[x][y+1]=i;
            y = y+1;
            change();
        }else if(labirent[x-1][y]==0){
            labirent[x-1][y]=i;
            x = x-1;
            change();
        }else if(labirent[x][y-1]==0){
            labirent[x][y-1]=i;
            y = y -1;
            change();
        }

}
void print(){

    for(int i=0;i<13;i++){
            for(int j=0;j<13;j++){
                printf("%d ",labirent[i][j]);
            }
            printf("\n");
        }

}

It works for this path, but how can i make a more general one? I could not understand stacks. I might use it if you can show me the way.

Edit: End point is added.

Thank you already.

I agree with @WeatherVane, it's unclear what you mean by 'works'. `change()` doesn't appear to be invoked, and looking at it, I'm pretty sure the only thing it would do is loop indefinitely. It will find a corner and then step in and out of it over and over again, won't it? Do you have a version that runs `change()`? — erik258, Dec 24 '16 at 18:59
You could have a look at [this answer](http://stackoverflow.com/a/34257513/4142924) and the earlier maze question in the duplicate linked. — Weather Vane, Dec 24 '16 at 19:00
http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze is a really interesting read — erik258, Dec 24 '16 at 19:05

user2736738 · Answer 1 · 2016-12-24T20:04:43.953

1

Considering there is a start and end point the solution is bfs run.(This is one of the solutions)

push s into queue with dist =0
and mark s visited
while( queue is not empty )
{
  x =   front(queue);
  remove x from queue
  foreach unvisited valid neighbor xn of x
      mark xn as visited 
      push it in queue with dist d+1 where d is dist from source to x.
}

edited Dec 24 '16 at 20:04

answered Dec 24 '16 at 19:01

user2736738

30,591
5
42
56

score 0 · Answer 2 · answered Dec 26 '16 at 18:58

0

Once, I had to do the same thing and the target of the exercise was implement the BackTracking algorithm: https://en.wikipedia.org/wiki/Backtracking

answered Dec 26 '16 at 18:58

ismatim

166
3
13

Finding Shortest Path In A Labyrinth with C

2 Answers2