c언어 자료구조 숙제 ~! 2부
요건좀 짧다 일부러 빠져나오는 구녕은 없게 만들었다 1로 둘러 쳤음
스택을 이용한 미로찾기!! 것도 C언어로...
XX캠퍼스인지 XXX 리포터 사이트라든지 엄청 나쁜거 같다.. 지식은 공유하는것이여~~
요런거가지고 대학생 돈 울궈먹는 사람 나쁘다 -..- 사는 사람도참.. @#$#@$?
주석까지 다달고 코딩까지 ..... D대학 다니시는 H님 잘참조 했습니다~~~
//미로찾기
//////////////////////////////////////////////////////////////////////////////////////////////////////////
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX_STACK_SIZE 200
#define MAX 20
#define FALSE 0
#define TRUE 1
//구조체 선언
typedef struct{
short int row;
short int col;
short int dir;
}element;
element stack[MAX_STACK_SIZE],position;
//탐색 경로
typedef struct{
short int vert;
short int horiz;
}offsets;
offsets move[8];
//함수 정의
void path(int (*maze)[MAX], int row, int col); //미로 탐색
void clear_kb(void); //메모리 초기화
element del(int *top); //탑 삭제
void add(int *top,element item); //스택 추가
main()
{
int i, j, row, col, maze[MAX][MAX]; //변수 선언
char func;
do
{
srand((unsigned)time(NULL)); //랜덤값 변화
//랜덤으로 미로를 무작위로 생성
printf("당신이 원하는 미로의 크기를 입력.(row,col):");
scanf("%d %d",&row, &col);
for(i=0; i<row; i++)
{
for(j=0;j<col; j++)
{
maze[i][j]=rand()%2;
} //미로를 랜덤으로 발생
}
for(i=0;i<col;i++) //벽은 모두 1로 채운다
{
maze[0][i]=1;
maze[row-1][i]=1;
}
for(i=0;i<row;i++)
{
maze[i][col-1]=1;
maze[i][0]=1;
}
maze[1][1]=0; //입구와 출구를 0으로 설정
maze[row-2][col-2]=0;
//미로 출력
printf("선택한 크기의 미로 생성.\n");
for(i=0; i<row; i++)
{
printf("\n");
for(j=0;j<col;j++)
{
printf("%2d",maze[i][j]);
}
}
printf("\n\n");
clear_kb(); //stdin상의 메모리를 초기화
printf("미로를 다시 생성 하시겠습니까?(y/n):");
scanf("%c",&func);
//y나n 이외의 값은 에러출력후 종료
if(!(func=='y'||func=='n'))
{
fprintf(stderr,"You must enter a \'x\' or \'y\'");
exit(1);
}
}while(func=='y'||func=='Y');
//미로 탐색
path(maze,row,col);
return 0;
}
//미로 탐색 알고리즘
void path(int (*maze)[MAX], int r, int c)
{
int i, j, top, row, col, next_row, next_col, dir, mark[MAX][MAX], found=FALSE;
//mark값을 초기화
for(i=0;i<MAX;i++)
{
for(j=0;j<MAX;j++)
{
mark[i][j]=0;
}
}
//move값 초기화
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;
//초기화 끝
mark[1][1]=1; //시작점을 1로 설정
top=0;
stack[0].row=1;
stack[0].col=1;
stack[0].dir=1;
while(top>-1&&!found)
{
position=del(&top);
row=position.row;
col=position.col;
dir=position.dir;
while(dir<8&&!found)
{
//dir을 북쪽에서 시계방향으로 돌리면서 탐색
next_row=row+move[dir-1].vert;
next_col=col+move[dir-1].horiz;
//만약 마지막 출구를 착았을때 found=1로 설정
if(next_row==r-2 && next_col==c-2)
found=TRUE;
else if(!maze[next_row][next_col]&&!mark[next_row][next_col])
{
mark[next_row][next_col]=1;
//그렇지 않은경우 경로 이동
position.row=row;
position.col=col;
position.dir=++dir;
add(&top,position);
row=next_row;
col=next_col;
dir=0;
}
else ++dir;
//dir 을 증가시켜 북쪽부터 시계방향으로 출구 검색
}
}
//출력 부분
if(found) //found가 1(TRUE)일때
{
printf("The path is:\n");
printf("row 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",r-2,c-2);
}
else
printf("The maze does not have a path\n");
}
// 스택 추가
void add(int *top,element item)
{
if(*top>=MAX_STACK_SIZE-1)
{
fprintf(stderr,"stack Is_Full.\n");
return;
}
stack[++*top]=item;
}
//스택 삭제
element del(int *top)
{
if(*top==-1)
{
printf("stack is empty.\n");
return stack[MAX_STACK_SIZE];
}
return stack[(*top)--];
}
void clear_kb(void)
{
char junk[80];
gets(junk);
}