MAZE Problem implementation in C Using Stack
#include
#include
int arr[100],top=-1,maxsize=100,color[50][50],visited[50][50];
int res[50][50];
int m,n;
int i,j;
int dest_i,dest_j;
void push(int x)
{
top++;
arr[top]=x;
}
int pop()
{
if(top==-1)
{
printf("empty");
return -1;
}
else
{
int x=arr[top];
top--;
return x;
}
}
void initialize()
{
int p,q;
for(p=0;p
for(q=0;q
color[p][q]=0;
visited[p][q]=0;
res[p][q]=0;
}
}
}
void color_mat()
{
int p,q;
for(p=0;p
for(q=0;q
printf("color of cell arr[%d][%d]",p,q);
scanf("%d",&color[p][q]);
}
}
}
void printSol()
{
int p,q;
for(p=0;p
for(q=0;q
printf("%d\t",res[p][q]);
}
printf("\n");
}
printf("\n");
printf("\n");
}
void printMat()
{
int p,q;
for(p=0;p
for(q=0;q
printf("%d\t",color[p][q]);
}
printf("\n");
}
printf("\n");
printf("\n");
}
int canMoveRight()
{
if((i
else
return -1;
}
int canMoveDown()
{
if(((i+1)
else
return -1;
}
int canMoveUp()
{
if(((i-1)>=0)&&(j
else
return -1;
}
int canMoveLeft()
{
if((i
return 1;
else
return -1;
}
void moveRight()
{
i=i;j=j+1;
res[i][j]=1;
visited[i][j]=1;
push(i);
push(j);
printSol();
}
void moveUp()
{
i=i-1;j=j;
res[i][j]=1;
visited[i][j]=1;
push(i);
push(j);
printSol();
}
void moveDown()
{
i=i+1;j=j;
res[i][j]=1;
visited[i][j]=1;
push(i);
push(j);
printSol();
}
void moveLeft()
{
i=i;j=j-1;
res[i][j]=1;
visited[i][j]=1;
push(i);
push(j);
printSol();
}
main()
{
printf("enter size of matrix");
scanf("%d%d",&m,&n);
initialize();
color_mat();
printf("enter destination");
scanf("%d%d",&dest_i,&dest_j);
i=0;j=0;
push(i);
push(j);
res[i][j]=1;
visited[i][j]=1;
while((i!=dest_i)||(j!=dest_j))
{
if(canMoveRight()==1)
{
printf("right \n");
moveRight();
}
else if(canMoveDown()==1)
{
printf("down \n");
moveDown();
}
else if(canMoveLeft()==1)
{
printf("left \n");
moveLeft();
}
else if(canMoveUp()==1)
{
printf("up \n");
moveUp();
}
else
{
printf("back \n");
if(top==-1)
{
printf("no solution \n");
break;
}
else
{
res[i][j]=0;
j=pop();
i=pop();
}
}
}
printf("\n Final Maritrix \n");
printMat();
printSol();
getch();
}
Posts
Please upload the algorithm also.....
ReplyDelete1.Set source as I,j and destination as dest_i,dest_j
ReplyDelete2.Push current position (I,j) to stack
3.Repeat until i==dest_i and j==dest_j
3.1.Move to right if right cell is not visited and color of right cell is 1.Push current location to stack
3.2.Else Move to down if down cell is not visited and color of down cell is 1. Push current location to stack
3.3.Move to left if left cell is not visited and color of left cell is 1. Push current location to stack
3.4.Move to up if up cell is not visited and color of up cell is 1. Push current location to stack
3.5.Else move to previous location while pop from stack. If Stack is empty then print “no Solution” and break
Some Conditions are missing in IF statement And FOR Loop.
ReplyDeletePlease update the same
Please Click the download link....and download the program.....
Delete