#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6

typedef struct {        // 교체!
	short r;
	short c;
} element;

typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType *s)
{
	s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 


element here = { 1,0 }, entry = { 1,0 };

char maze[MAZE_SIZE][MAZE_SIZE] = {
{ '1', '1', '1', '1', '1', '1' },
{ 'e', '0', '1', '0', '0', '1' },
{ '1', '0', '0', '0', '1', '1' },
{ '1', '0', '1', '1', '1', '1' },
{ '1', '0', '0', '0', '0', 'x' },
{ '1', '1', '1', '1', '1', '1' },
};
// 위치를 스택에 삽입
void push_loc(StackType *s, int r, int c)
{
	if (r < 0 || c < 0) return;
	if (maze[r][c] != '1' && maze[r][c] != '.') {
		element tmp;
		tmp.r = r;
		tmp.c = c;
		push(s, tmp);
	}
}
// 미로를 화면에 출력한다. 
void maze_print(char maze[MAZE_SIZE][MAZE_SIZE])
{
	printf("\n");
	for (int r = 0; r < MAZE_SIZE; r++) {
		for (int c = 0; c < MAZE_SIZE; c++) {
			printf("%c", maze[r][c]);
		}
		printf("\n");
	}
}
int path_length = 0;
void backtracking_load(StackType *s, int r, int c, StackType *sm)
{
	element next, tmp;

	if ((maze[r - 1][c] == '1' || maze[r - 1][c] == '.') &&
		(maze[r + 1][c] == '1' || maze[r + 1][c] == '.') &&
		(maze[r][c - 1] == '1' || maze[r][c - 1] == '.') &&
		(maze[r][c + 1] == '1' || maze[r][c + 1] == '.')) { // 막다른 곳
		next = peek(s);
		do {
			tmp = pop(sm);
			path_length--;
			if ((abs(tmp.c - next.c) + abs(tmp.r - next.r)) == 1) {// backtracking 위치 찾음
				push(sm, tmp);
				break;
			}
		} while (1);
	}
}

void print_path(StackType *sm)
{
	int i;
	element tmp;

	printf("출구->");
	for (i = 0; i < path_length; i++) {
		tmp = pop(sm);
		printf("(%d,%d)", tmp.r, tmp.c);
	}
	printf("->입구\n");
}

int main(void)
{
	int r, c;
	StackType s, sm;

	init_stack(&s);
	init_stack(&sm);
	here = entry;
	while (maze[here.r][here.c] != 'x') {
		r = here.r;
		c = here.c;

		maze[r][c] = '.';
		maze_print(maze);

		push_loc(&s, r - 1, c);
		push_loc(&s, r + 1, c);
		push_loc(&s, r, c - 1);
		push_loc(&s, r, c + 1);

		element tmp;
		tmp.r = r;
		tmp.c = c;
		push(&sm, tmp);
		path_length++;
		backtracking_load(&s, r, c,&sm);

		if (is_empty(&s)) {
			printf("실패\n");
			return;
		}
		else
			here = pop(&s);
	}
	printf("성공\n");
	print_path(&sm);
	return 0;
}