#include <stdio.h>
#include<time.h>
#include<stdlib.h>
#define numRow 10
#define numCol 10
#define MAX_STACK_SIZE 100 //스택의 최대 크기
#define TRUE 1 //TRUE의 초기화
#define FALSE 0 //FALSE의 초기화
#define MARK 2 //가본 길 기록
#define EXIT_ROW 8
#define EXIT_COL 7
short int maze[numRow + 2][numCol + 2];
int top = -1;
typedef struct {
short int vert;
short int horiz;
}offsets;
offsets move[8] = { { -1, 0 },
{ -1,1 },
{ 0,1 },
{ 1,1 },
{ 1,0 },
{ 1,-1 },
{ 0,-1 },
{ -1,-1 }
};
typedef struct {
short int row;
short int col;
short int dir;
}element1;
element1 stack1[MAX_STACK_SIZE]; //지나온 경로와 방향을 저장할 stack
void setmaze();
void path();
void push(element1);
element1 pop();
int main() {
setmaze();
for (int i = 0; i < numRow + 2; i++) {
for (int j = 0; j < numCol + 2; j++)
printf("%2d", maze[i][j]);
printf("\n");
}
path();
for (int i = 0; i < numRow + 2; i++) {
for (int j = 0; j < numCol + 2; j++)
printf("%2d", maze[i][j]);
printf("\n");
}
return 0;
}
void setmaze() {
short int maze0[numRow][numCol] = {
{ 0,0,1,1,1,0,1,0,1,0 },
{ 1,0,0,1,1,1,0,1,0,1 },
{ 1,1,0,1,1,0,1,0,1,1 },
{ 0,0,1,1,0,0,1,0,0,0 },
{ 1,1,0,1,1,0,1,0,1,0 },
{ 1,0,1,1,0,1,1,0,0,1 },
{ 1,1,0,1,0,1,0,0,1,1 },
{ 1,0,1,0,1,0,1,0,0,0 },
{ 0,1,0,1,1,1,0,1,1,0 },
{ 1,0,0,1,1,1,0,0,0,0 }
};
for (int i = 0; i < numCol + 2; i++) {
maze[0][i]= maze[numRow + 1][i] = maze[i][0] = maze[i][numCol + 1] = 1;
}
for (int i = 1;i < numRow + 1 ; i++) {
for (int j = 1; j < numCol + 1; j++) {
maze[i][j] = maze0[i - 1][j - 1];
}
}
}
void path() { //미로탐색
int row = 0;
int col = 0;
int nextRow = 0;
int nextCol = 0;
int dir = 0;
int found = FALSE;
element1 position;
srand((unsigned int)time(NULL));
maze[1][1] = MARK; top = 0;
stack1[0].row = 1;
stack1[0].col = 1;
stack1[0].dir = rand() % 8;
int count = 0;
while (top > -1 && !found)
{
position = pop();
row = position.row;
col = position.col;
dir = rand() % 8;
while (dir < 8 && !found)
{
nextRow = row + move[dir].vert;
nextCol = col + move[dir].horiz;
if (!maze[nextRow][nextCol] && (EXIT_ROW - 1 <= nextRow && nextRow <= EXIT_ROW + 1 ) && (EXIT_COL - 1 <= nextCol && nextCol <= EXIT_COL + 1))
{
found = TRUE;
}
else if (maze[nextRow][nextCol] == FALSE)
{
maze[nextRow][nextCol] = MARK;
position.row = row;
position.col = col;
//position.dir = ++dir;
push(position);
row = nextRow;
col = nextCol;
}
else
{
dir = rand()%8;
printf("%d ", rand() % 8);
}
if(count >= 100)
{
found = TRUE;
count = 0;
}
count++;
}
}
if (found) {
printf("The path is:\n\n");
printf("row col\n");
for (int i = 0; i <= top; i++)
printf("%2d%5d\n", stack1[i].row, stack1[i].col);
printf("%2d%5d\n", row, col);
printf("%2d%5d\n", nextRow, nextCol);
printf("%2d%5d\n", EXIT_ROW, EXIT_COL);
}
else printf("The maze does not have a path.\n");
}
void push(element1 it) {
if (top >= MAX_STACK_SIZE - 1)
printf("stack if Full");
stack1[++top] = it;
}
element1 pop() {
if (top == -1)
printf("stack is Empty");
return stack1[top--];
}