SHORTEST PATH PROGRAMME

/* This program finds the paths(atleast the best path) between the
   specified source(Src) and destination(Dst) points in the maze
defined
   below(Maze).

   A '0' means we can move and '1' means we can't move.

   You can change the variables Src, Dst below to change
source/destination.

   This is an application to demonstrate search trees, where the tree
is
   organised in an array.
*/



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

#define MAX_ROW 7
#define MAX_COL 8
#define MAX_RECORDED_MOVES 1000
#define MAX_LEVELS  500
#define PATH    '0'


typedef unsigned int uint32;

typedef struct __Cell {

uint32 row;
uint32 col;
}Cell;

typedef enum {
LEFT,
RIGHT,
UP,
DOWN
}move_t;

typedef struct {

uint32 base_choice_id;
uint32 num_options;
}level_t;

typedef struct {

Cell   cell;
uint32 num_moves;
move_t move;
}choice_t;

typedef struct {

Cell   cell;
uint32 num_moves;

}record_t;

record_t _records[MAX_RECORDED_MOVES];
choice_t _choices[MAX_RECORDED_MOVES];
level_t  _levels[2000];

uint32 _num_records=0,num_solutions=0;

Cell Src = { 0,1 }, Dst = { 4,3};

char Maze[MAX_ROW][MAX_COL+1] = {
 "0*000000",
 "01011110",
 "00001110",
 "01101000",
 "000*1101",
 "11111100",
 "11111110"
};

uint32 move_is_okay(move_t move, choice_t *choice)
{
uint32 row = choice->cell.row;
uint32 col = choice->cell.col;

switch(move)
{
case LEFT:
   if(col == 0)
{
return 0;
}
   col--;
break;
case RIGHT:
if(col == MAX_COL-1)
{
return 0;
}
   col++;
break;
case DOWN:
if(row == MAX_ROW-1)
{
return 0;
}
   row++;
break;
case UP:
if(row == 0)
{
return 0;
}
   row--;
break;
default:
printf(" invlid move
");
exit(0);
}

if(Maze[row][col] == PATH)
{
choice->cell.row = row;
choice->cell.col = col;
return 1;
}

return 0;
}

uint32 reached_the_target(Cell cell)
{
return (cell.row == Dst.row) && (cell.col == Dst.col);
}


uint32 record_move(choice_t *choice)
{
uint32 index;

for(index=0;index<_num_records;index++)
{
if((_records[index].cell.col == choice->cell.col) &&
  (_records[index].cell.row == choice->cell.row) )
{
if(_records[index].num_moves < choice->num_moves)
{
return 0;
}

_records[index].num_moves = choice->num_moves;
return 1;
}
}

_records[_num_records].cell = choice->cell;
_records[_num_records].num_moves = choice->num_moves;
_num_records++;
if(_num_records == MAX_RECORDED_MOVES)
{
printf("
Insufficient memory
");
exit(1);
}

return 1;
}

void print_path(level_t *final)
{
level_t *level;

choice_t *choice;
char *moves[] = { "LEFT","RIGHT","UP","DOWN"};

printf("   Found a path with %d moves
", final-&_levels[0]+1);
for(level = &_levels[0];level <= final; level++)
{
   choice = &_choices[level->base_choice_id + level->num_options];
printf("Move : %s
",moves[choice->move]);
}
num_solutions++;
}

uint32 expand_level(level_t *level, uint32 base_choice_id)
{
choice_t *choice,base_choice;
uint32 choice_id;
move_t move;

level->base_choice_id = base_choice_id;
level->num_options = 0;

base_choice = _choices[base_choice_id];

choice_id = base_choice_id+1;
choice = &_choices[choice_id];

for(move = LEFT; move<= DOWN; move++)
{
*choice = base_choice;
choice->num_moves++;
if(move_is_okay(move,choice))
{
choice->move = move;

if(reached_the_target(choice->cell))
{
level->num_options++;
print_path(level);
level->num_options--;
}
else
{
if(record_move(choice))
{
choice++;
if(choice == &_choices[MAX_RECORDED_MOVES-1])
{
printf("
 Insufficient memory..
");
exit(1);
}
level->num_options++;
}
}
}
}

return level->num_options;
}

void main()
{
uint32 base_choice_id;
uint32 moves,Done=0;
level_t *level;

base_choice_id = 0;
level = &_levels[0];

_choices[0].cell = Src;
_choices[0].num_moves = 0;
Maze[Dst.row][Dst.col] = '0';

while(!Done)
{
moves = expand_level(level,base_choice_id);

if(moves)
{
base_choice_id +=moves;
level++;
if(level > &_levels[MAX_LEVELS-1])
{
printf("
 Insufficient memory..
");
exit(1);
}
}
else
{
while(level != &_levels[0])
{
level--;
base_choice_id--;
level->num_options--;
if(level->num_options)
{
level++;
break;
}
}

if(base_choice_id == 0)
{
printf("
     Search found %d solutions
",num_solutions);
break;
}
}
}
getchar();
}