- Write a program to solve a path in a maze based on a stack. The program should contain the following functions:
a) Provide an interface for user to initial the maze array by input from keyboard or scanning from file.
b) Write the normal routines of array stack, i.e., Push(), Pop(), Top(), etc.
c) Write a Soluation() routine which solves the path problem by calling the normal routines.
d) Output the maze in form of matrix on screen.
e) Output the path, e.g., (6,8)←(3, 4)←, …, on screen.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
typedef struct
{
int c;
int r;
}Position; //(c,r)
typedef struct
{
Position seat; //Position before next step
int direction; //1 for up,2 for right,3 for down,4 for left,0 for undetermined
}Solution;
typedef struct
{
Solution* data;
int numofsteps;
}Solutions;
typedef struct
{
int Column;
int Row;
int** Arr;
}Maze;
Position* Move(int direction,Position seat,Maze* maze){
Position* newseat;
newseat = (Position*) malloc(sizeof(Position));
*newseat = seat;
if(direction == 1) newseat -> r --;
if(direction == 3) newseat -> r ++;
if(direction == 2) newseat -> c ++;
if(direction == 4) newseat -> c --;
if((newseat -> r <0)||(newseat -> r >= maze->Row)||(newseat -> c <0)||(newseat -> c >= maze->Column)){
free(newseat);
newseat = NULL;
return NULL;
}
if(maze->Arr[newseat->c][newseat->r] == 1){
free(newseat);
newseat = NULL;
return NULL;
}
else return newseat;
}
int IsPossible(Solution* a,Maze* maze){
Position* newseat;
newseat = Move(a->direction,a->seat,maze);
if(newseat == NULL) return 0;
if(maze->Arr[newseat->c][newseat->r] == 1) return 0;
if(maze->Arr[newseat->c][newseat->r] == 0) return 1;
}
Solution* Top(Solutions* a){
return &(a->data[a->numofsteps]);
}
Solutions* Push(Solutions* s,Solution* sol){
{
Solution* TmpCell;
TmpCell = (Solution*) malloc(sizeof(Solution));
if(TmpCell == NULL){
printf("Out of space!!!\n");
}
else{
TmpCell->direction = sol->direction;
TmpCell->seat = sol->seat;
s->numofsteps ++;
s->data[s->numofsteps] = *TmpCell;
free(TmpCell);
TmpCell =NULL;
}
return s;
}
}
Solutions* Pop(Solutions* s){
{
if(s->numofsteps==0){
printf("Empty!\n");
}
else{
s->numofsteps --;
}
}
}
void Printposition(Position* p){
printf("(%d,%d)",p->c,p->r);
}
int IsIdentical(Position* a,Position* b){
if((a->c==b->c)&&(b->r==a->r)) return 1;
else return 0;
}
int EverBeen(Solutions* s,Position* p,Maze* maze){
int i;
for(i=s->numofsteps;i>=1;i--){
if(IsIdentical(&s->data[i].seat,p)) return 1;
}
return 0;
}
Solutions* SolveMaze(Maze* maze,Position* start,Position* end){
Solutions* s;
Solution* trial;
s = (Solutions*) malloc(sizeof(Solutions));
trial = (Solution*) malloc(sizeof(Solution));
s ->numofsteps = 1;
s ->data = (Solution*) malloc(maze->Column*maze->Row*sizeof(Solution));
s -> data[1].seat = *start;
s -> data[1].direction = 0;
while(!IsIdentical(Move(Top(s)->direction,Top(s)->seat,maze),end)){
Top(s)->direction =1;
//Printposition(Move(1,Top(s)->seat,maze));
if((IsPossible(Top(s),maze))&&(!EverBeen(s,Move(1,Top(s)->seat,maze),maze))){
trial ->direction =0;
trial ->seat = *Move(1,Top(s)->seat,maze);
Push(s,trial);
continue;
}
Top(s)->direction =2;
//Printposition(Move(2,Top(s)->seat,maze));
if((IsPossible(Top(s),maze))&&(!EverBeen(s,Move(2,Top(s)->seat,maze),maze))){
trial ->direction =0;
trial ->seat = *Move(2,Top(s)->seat,maze);
Push(s,trial);
continue;
}
Top(s)->direction =3;
//Printposition(Move(3,Top(s)->seat,maze));
if((IsPossible(Top(s),maze))&&(!EverBeen(s,Move(3,Top(s)->seat,maze),maze))){
trial ->direction =0;
trial ->seat = *Move(3,Top(s)->seat,maze);
Push(s,trial);
continue;
}
Top(s)->direction =4;
//Printposition(Move(4,Top(s)->seat,maze));
if((IsPossible(Top(s),maze))&&(!EverBeen(s,Move(4,Top(s)->seat,maze),maze))){
trial ->direction =0;
trial ->seat = *Move(4,Top(s)->seat,maze);
Push(s,trial);
continue;
}
Pop(s);
if(s->numofsteps==0) return NULL;
}
return s;
} //Function for solving the maze
void PrintMaze(Maze* maze){
int i,j;
for(i=0;i<maze->Row;i++){
for(j=0;j<maze->Column;j++){
if(maze -> Arr[j][i] == 0)printf("□");
if(maze -> Arr[j][i] == 1)printf("■");
}
printf("\n");
}
}
void PrintSolutions(Solutions* s,Position* end){
while(s->numofsteps !=0){
if(!IsIdentical(&(Top(s)->seat),end)) printf("←");
Printposition(&(Top(s)->seat));
Pop(s);
}
}
/**void PrintSolutionsInGraph(Solutions* s,Position* end,Maze* maze){
int i,j;
maze->Arr[end->c][end->r] = s->numofsteps +1;
for(i = s->numofsteps;i>=0;i--){
if(i!=1) maze->Arr[Top(s)->seat.c][Top(s)->seat.r] = i;
else maze->Arr[Top(s)->seat.c][Top(s)->seat.r] = -1;
Pop(s);
}
for(i=0;i<maze->Row;i++){
for(j=0;j<maze->Column;j++){
if(maze -> Arr[i][j] == 0)printf("□");
if(maze -> Arr[i][j] == 1)printf("■");
if(maze -> Arr[i][j] == -1)printf("1");
else printf("%d",maze -> Arr[i][j]);
}
printf("\n");
}
}
**/ //Trying to print it in a more clear way but failed
int main(){
int row,column,i,j,k;
Maze* maze;
int** r;
Position* p,*start,*end;
Solutions* solutionset;
start = (Position*) malloc(sizeof(Position));
end = (Position*) malloc(sizeof(Position));
maze = (Maze*) malloc(sizeof(Maze));
printf("Input the numbers of rows and columns in 'row,column' format.");
scanf("%d,%d",&row,&column);
maze->Row = row;
maze->Column = column;
r = (int**) malloc(row * sizeof(int*));
for (i = 0; i < column; i++){
r[i] = (int*) malloc(column * sizeof(int));
}
//Construct the initial maze
printf("Input the maze using 1 for wall and 0 for vacancy,use commas to seperate numbers.\n");
for(i=0;i<row;i++){
for(j=0;j<column;j++){
scanf("%d,",&r[j][i]);
}
}
maze -> Arr = r;
PrintMaze(maze);
printf("Now input the start point. Note that the one in the top left corner is 0,0 ");
scanf("%d,%d",&start->c,&start->r);
while(maze->Arr[start->c][start->r] == 1) {
printf("Invalid!");
printf("Now input the start point. Note that the one in the top left corner is 0,0 ");
scanf("%d,%d",&start->c,&start->r);
}
printf("Now input the end point. Note that the one in the top left corner is 0,0 ");
scanf("%d,%d",&end->c,&end->r);
while(maze->Arr[end->c][end->r] == 1) {
printf("Invalid!");
printf("Now input the end point. Note that the one in the top left corner is 0,0 ");
scanf("%d,%d",&end->c,&end->r);
}
//Solve
solutionset = SolveMaze(maze,start,end);
PrintSolutions(solutionset,end);
printf("\n");
/**PrintSolutionsInGraph(solutionset,end,maze);**/
scanf("%d",&i);
return 0;
}
