A Mazing Problem
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
short int vert;
short int horiz;
}Offsets;
Offsets move[8];
typedef struct
{
short int row;
short int col;
short int dir;
}Element;
Element Stack[50];
int maze[10][10];
int mark[10][10];
int top=-1;
int exit_row,exit_col;
void readMaze()
{
int r, c;
int i, j;
printf("\nEnter the no of rows in the matrix: ");
scanf("%d", &r);
printf("\nEnter the no of cols in the matrix: ");
scanf("%d",&c);
printf("\nEnter the elements of the matrix: ");
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%d",&maze[i][j]);
}
}
exit_row = r-2;
exit_col = c-2;
}
void setMoveTable()
{
move[0].vert = -1, move[0].horiz = 0;
move[1].vert = -1, move[1].horiz = 1;
move[2].vert = 0, move[2].horiz = 1;
move[3].vert = 1, move[3].horiz = 1;
move[4].vert = 1, move[4].horiz = 0;
move[5].vert = 1, move[5].horiz = -1;
move[6].vert = 0, move[6].horiz = -1;
move[7].vert = -1, move[7].horiz = -1;
}
void push(Element ele)
{
top = top+1;
Stack[top].row = ele.row;
Stack[top].col = ele.col;
Stack[top].dir = ele.dir;
return;
}
Element pop()
{
Element delItem;
delItem.row = Stack[top].row;
delItem.col = Stack[top].col;
delItem.dir = Stack[top].dir;
top = top-1;
return delItem;
}
void findpath()
/* function to search for path in the maze */
{
int i,row,col,nextRow,nextCol,dir,found=0;
Element position;
mark[1][1] = 1,top=0;
Stack[0].row = 1;
Stack[0].col = 1;
Stack[0].dir = 0;
while(top>-1 && !found)
{
position = pop();
row = position.row;
col = position.col;
dir = position.dir;
while(dir<8 && !found)
{
nextRow = row + move[dir].vert;
nextCol = col + move[dir].horiz;
if(nextRow == exit_row && nextCol == exit_col)
found = 1;
else if(!maze[nextRow][nextCol] && !mark[nextRow][nextCol])
{
mark[nextRow][nextCol] = 1;
position.row = row;
position.col = col;
position.dir = ++dir;
push(position);
row = nextRow;
col = nextCol;
dir = 0;
}
else
++dir;
}
}
if(found)
{
printf("\nThe path is:\n");
printf("row \t col \n");
for(i=0;i<=top;i++)
printf("%2d%5d \n",Stack[i].row,Stack[i].col);
printf("%2d%5d\n",row,col);
printf("%2d%5d\n",exit_row,exit_col);
}
else
printf("\nThe given maze does not have a path");
}
void main()
{
readMaze();
setMoveTable();
findpath();
return;
}
Output:
just put 1s for indicating border/wall (blue color)
Enter the no of rows in the matrix: 11
Enter the no of cols in the matrix: 8
Enter the elements of the matrix:
1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1
1 1 1 1 1 1 0 1
1 1 0 0 0 0 1 1
1 0 1 1 1 1 1 1
1 1 0 0 0 0 1 1
1 1 1 1 1 1 0 1
1 1 0 0 0 0 1 1
1 0 1 1 1 1 1 1
1 1 0 0 0 0 0 1
1 1 1 1 1 1 1 1
The path is:
row col
1 1
1 2
1 3
1 4
1 5
2 6
3 5
3 4
3 3
3 2
4 1
5 2
5 3
5 4
5 5
6 6
7 5
7 4
7 3
7 2
8 1
9 2
9 3
9 4
9 5
9 6
Credits,
Manoj T
