Skip to content

Instantly share code, notes, and snippets.

@a3f
Last active August 29, 2015 14:20
Show Gist options
  • Save a3f/22af62ec39e1fc9556f8 to your computer and use it in GitHub Desktop.
Save a3f/22af62ec39e1fc9556f8 to your computer and use it in GitHub Desktop.
Find all paths from that lead outside the maze starting from a given position
#include <stdio.h>
#include <stdlib.h>
#define I_MAX 11
#define J_MAX 8
enum {FREE = 0, BLOCKED = 1, END = 2, DONE, SOLUTION};
int maze[I_MAX][J_MAX] = {
{1, 0, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 1, 1, 1},
{1, 1, 0, 0, 1, 0, 1, 1},
{1, 0, 1, 0, 1, 1, 1, 1},
{1, 1, 0, 0, 0, 0, 1, 1},
{1, 1, 0, 1, 1, 1, 1, 1},
{1, 1, 0, 0, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 1, 0, 1},
{1, 1, 0, 1, 0, 0, 1, 1},
{1, 1, 0, 1, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 0, 1}
};
#define follow(i,j) recursive_follow(i,j,1)
void recursive_follow(unsigned, unsigned, int);
void print_maze()
{
int i,j;
for (i = 0; i < I_MAX; i++, putchar('\n'))
for (j = 0; j < J_MAX; j++)
printf("%d ", maze[i][j]);
}
int main(void)
{
print_maze();
follow(0,1);
}
void recursive_follow(unsigned i, unsigned j, int first_run)
{
if (i > I_MAX || j > J_MAX || maze[i][j] != FREE )
return;
if ((i == I_MAX || j == J_MAX || i == 0 || j == 0) && !first_run)
{
puts("target reached");
print_maze();
//exit(1);
return;
}
maze[i][j] = SOLUTION;
recursive_follow(i-1,j,0);
recursive_follow(i+1,j,0);
recursive_follow(i,j+1,0);
recursive_follow(i,j-1,0);
maze[i][j] = DONE;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment