#include <stdio.h>//5396952 이현민
#include <string.h>
#include <stdlib.h>
#define MAZE_SIZE 6
#define MAX_STACK_SIZE 100
typedef struct {
short r;
short c;
} location;
typedef struct {
location stack[MAX_STACK_SIZE];
int top;
}StackType;
location here = {1,0};
location entry = {1,0};
//initiating entry and start point, those are containing garbage values
char maze [MAZE_SIZE][MAZE_SIZE] = {
{ '1','1','1','1','1','1'},
{ 'e','0','0','0','0','1'},
{ '1','0','1','0','1','1'},
{ '1','1','1','0','0','x'},
{ '1','1','1','0','1','1'},
{ '1','1','1','1','1','1'},
};
void init(StackType *s)
{
s->top = -1;
}
int isEmpty(StackType *s)
{
return (s->top == -1);
}
int isFull(StackType *s)
{
return (s->top == (MAX_STACK_SIZE -1));
}
void push(StackType *s, location item)
{
if(isFull(s) == -1)
{
fprintf(stderr,"stack full error\n");
return;
}
else{
s->stack[++(s->top)] = item;
}
//push saves available location
}
location pop(StackType *s)
{
if(isEmpty(s) == -1)
{
fprintf(stderr, "stack empty error\n");
exit(1);
}
else return (s->stack[ (s->top)-- ]);
}
location peek(StackType *s)
{
if(isEmpty(s) == -1)
{
fprintf(stderr, "stack empty error\n");
exit(1);
}
else return (s->stack[s->top]);
}
void push_loc (StackType *s, int r, int c){
if( r < 0 || c < 0)//if scanning spot is out of maze, finish scanning
return;
//if the spot was not visited and not a wall but something else, even not a path
if( maze[r][c] != '1' && maze[r][c] != '.')
{
location tmp;//move the rat to scanned spot
tmp.r = r;
tmp.c = c;
/*why do we need tmp struct type?
to save new spot's location in same datastructure and pass it to push directly */
push(s, tmp);
}
}
void recur(StackType *s, int index){
printf("Tracker : (%d , %d) index %d\n", s->stack[index].r, s->stack[index].c, index);
if( index != 0){
recur(s, index -1);
}
}
void main(){
int r;
int c;
StackType s;
StackType tracker;
init(&s);
init(&tracker);
here = entry;
printf("미로찾기\n");
while(maze[here.r][here.c] != 'x')
{
r = here.r;
c = here.c;//location right now
maze[r][c] = '.';
push_loc(&s, r-1, c);//top
push_loc(&s, r+1, c);//bottom
push_loc(&s, r, c-1);//left
push_loc(&s, r, c+1);//right
//push_loc will succeed when there is available path to go
if(isEmpty(&s))
{
fprintf(stderr,"no more stack data\n");
return;
}
/*stack is not empty but there were no cell available
go to the spot that the mice haven't visited yet*/
else{
here = pop(&s);
push(&tracker, here);
}
printf("Mice : (%d , %d) \n", here.r, here.c, s.top);
//actually move the location of mice and remove tha location from the stack
}
/*//iritational way to print out the tracker
for(int i = 0; i<= tracker.top; i++)
{
printf("Tracker :(%d , %d) ,top = %d\n", tracker.stack[tracker.top - i].r, tracker.stack[tracker.top - i ].c, tracker.top - i);
}
*/
printf("되돌아나오는 경로\n");
recur(&tracker, tracker.top);
}
/*되돌아나오는 경로를 저장하기위한 스택을 위해 따로 push와 pop을 구현할 필요는 없었습니다
어떻게해야할지모르겠어요~.*/
#include <string.h>
#include <stdlib.h>
#define MAZE_SIZE 6
#define MAX_STACK_SIZE 100
typedef struct {
short r;
short c;
} location;
typedef struct {
location stack[MAX_STACK_SIZE];
int top;
}StackType;
location here = {1,0};
location entry = {1,0};
//initiating entry and start point, those are containing garbage values
char maze [MAZE_SIZE][MAZE_SIZE] = {
{ '1','1','1','1','1','1'},
{ 'e','0','0','0','0','1'},
{ '1','0','1','0','1','1'},
{ '1','1','1','0','0','x'},
{ '1','1','1','0','1','1'},
{ '1','1','1','1','1','1'},
};
void init(StackType *s)
{
s->top = -1;
}
int isEmpty(StackType *s)
{
return (s->top == -1);
}
int isFull(StackType *s)
{
return (s->top == (MAX_STACK_SIZE -1));
}
void push(StackType *s, location item)
{
if(isFull(s) == -1)
{
fprintf(stderr,"stack full error\n");
return;
}
else{
s->stack[++(s->top)] = item;
}
//push saves available location
}
location pop(StackType *s)
{
if(isEmpty(s) == -1)
{
fprintf(stderr, "stack empty error\n");
exit(1);
}
else return (s->stack[ (s->top)-- ]);
}
location peek(StackType *s)
{
if(isEmpty(s) == -1)
{
fprintf(stderr, "stack empty error\n");
exit(1);
}
else return (s->stack[s->top]);
}
void push_loc (StackType *s, int r, int c){
if( r < 0 || c < 0)//if scanning spot is out of maze, finish scanning
return;
//if the spot was not visited and not a wall but something else, even not a path
if( maze[r][c] != '1' && maze[r][c] != '.')
{
location tmp;//move the rat to scanned spot
tmp.r = r;
tmp.c = c;
/*why do we need tmp struct type?
to save new spot's location in same datastructure and pass it to push directly */
push(s, tmp);
}
}
void recur(StackType *s, int index){
printf("Tracker : (%d , %d) index %d\n", s->stack[index].r, s->stack[index].c, index);
if( index != 0){
recur(s, index -1);
}
}
void main(){
int r;
int c;
StackType s;
StackType tracker;
init(&s);
init(&tracker);
here = entry;
printf("미로찾기\n");
while(maze[here.r][here.c] != 'x')
{
r = here.r;
c = here.c;//location right now
maze[r][c] = '.';
push_loc(&s, r-1, c);//top
push_loc(&s, r+1, c);//bottom
push_loc(&s, r, c-1);//left
push_loc(&s, r, c+1);//right
//push_loc will succeed when there is available path to go
if(isEmpty(&s))
{
fprintf(stderr,"no more stack data\n");
return;
}
/*stack is not empty but there were no cell available
go to the spot that the mice haven't visited yet*/
else{
here = pop(&s);
push(&tracker, here);
}
printf("Mice : (%d , %d) \n", here.r, here.c, s.top);
//actually move the location of mice and remove tha location from the stack
}
/*//iritational way to print out the tracker
for(int i = 0; i<= tracker.top; i++)
{
printf("Tracker :(%d , %d) ,top = %d\n", tracker.stack[tracker.top - i].r, tracker.stack[tracker.top - i ].c, tracker.top - i);
}
*/
printf("되돌아나오는 경로\n");
recur(&tracker, tracker.top);
}
/*되돌아나오는 경로를 저장하기위한 스택을 위해 따로 push와 pop을 구현할 필요는 없었습니다
어떻게해야할지모르겠어요~.*/
댓글
댓글 쓰기