#include <stdio.h>
#include <dos.h>
#include <conio.h>
#include <bios.h>
#include <stdlib.h>

#define MAZE_SIZE	19                    // 전역변수 선언 (일명 : 전처리문) 
#define ROBOT		2
		/* 얼굴 모양의 ASCII 코드 */

int maze [MAZE_SIZE] [MAZE_SIZE] =					//미로의 모양  
{                                                   // int형의 2차원 19행 19열의 배열  maze의 대한 초기화  
	{ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},       // 1이면 벽 이고, 0이면 미로 자세히 보면 미로 처럼 보임 
	{ 0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1},
	{ 1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1},
	{ 1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1},
	{ 1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
	{ 1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1},
	{ 1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1},
	{ 1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1},
	{ 1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1},
	{ 1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1},
	{ 1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1},
	{ 1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,1,0,1},
	{ 1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
	{ 1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1},
	{ 1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1},
	{ 1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1},
	{ 1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,0,1},
	{ 1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
	{ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};

int sx = MAZE_SIZE - 1, sy = MAZE_SIZE - 2;	// 생쥐의 출발 위치 , 미로의 모양을 보면 오른쪽 하단이 생쥐의 출발 위치다. 그래서 x,y좌표값을 입력하고 있다. 

int *rec;		// 최단 경로 계산을 위해 생쥐가 움직인 경로를 저장  , rec라는 int형의 포인터 선언. 포인터의 개념을 모르겠어면 물어봐라. 내말고.. ^^ 

#define UP	1
#define RIGHT	2
#define DOWN	4
#define LEFT	8

               // main을 분석하다 보면 알게 될테지만 UP,RIGHT,DOWN, LEFT는 앞으로 전개될 프로그램에서 아주 중요한 값이다. 

int get_shape ( int m[] [MAZE_SIZE], int x, int y)     // int형의 함수 get_shape()를 만든다. 인자(함수가 호출한 함수로 부터 받는 초기화 된값, 
                                                       // 앞으로 계산할값_)는 int m[] [MAZE_SIZE], int x, int y로 받고 있다.  
{
	// 벽배치에 따른 중앙벽의 모양을 리턴 
	
	static shape[] = { 32,179,196,192,179,179,218,195,196,217,196,193,191,180,194,179};

	int s = 0;
	if (m[y][x])
	{
		if (y > 0 && m[y-1] [x]) s |= UP;
		if (y < MAZE_SIZE - 2 && m[y+1][x]) s |= DOWN;
		if (x > 0 && m[y][x-1]) s |=LEFT;
		if (x < MAZE_SIZE - 2 && m[y] [x+1]) s |= RIGHT;
	}
	return shape [s];
}

void draw_maze(int m[] [MAZE_SIZE])               // draw_maze()함수의 형태에 대해서 살펴봅시다. 먼저 함수의 데이터혀이 왜 void입니까? 
                                                  // 1,2,3,4, "늦어서! 0.4초안에 말이 틔어 나와야 되. 여러분 공부 그런 식으로 하면 안되요 -mr.choi-"
                                                  // 함수의 인자 (int m[][MAZE_SIZE])이놈에 대해서 이해합니까? 이함수는 RETURN값이 있을까, 없을까 ? 있다면 왜,, 없다면 왜? 모르겠습니까? ^^;  "늦어서! 0.4초안에 말이 틔어 나와야 되. 여러분 공부 그런 식으로 하면 안되요 -mr.choi-"
{
	// 미로를 화면에 그려줌
	int i, j;                                     // 지역 변수 I와J를 선언 
	for (j = 0; j<MAZE_SIZE; j++)                 // 먼저 , 이 함수에 있는 이중 FOR문이 무엇을 하는 놈이지 고민해 보자.
    	for (i = 0; i<MAZE_SIZE; i++)             // 먼저 FOR문 안의 FOR문 은 I를 19번 찍고 나가면 J가 한번 찍인 꼴이 된다. 이 함수가 종료되어 MAIN으로 넘어가려면, J가 19번 찍혀야 끝난다. 즉 무슨 말인고 하니  (J == 19I) * 19 가 되어야 이함수가 쫑나서 MAIN으로 돌아간다는 말이다. 
		{                                         // "그라면 좋다  C바 (J == 19I) * 19만큼의 횟수 동안 도대체 무슨일을 하는데" 라고 묻고 싶죠? I변수의 FOR문에 있는 단 2행의 프로그램이 그 답이다.  
			gotoxy(i+1,j+1);              // gotoxy()함수로 간다. (전문용어로 호출한다 라고 한다.) 뭐해 안가고... ㅋㅋ 미안 내가 어제 밤에 졸다가 쳤더니 gotoxy()가 빠졌는 모양이다. 좌표를 그려주는 함수겠죠.
           
			putch(get_shape(m, i, j));     // get_shape(m,i,j)함수를 인자로 받고 있으므로  get_shape()함수를 호출한다.  
		}
}

void record(int x, int y)
{
	// 생쥐의 이동경로를 저장
	static int index = 0;
	rec[index++] = x;
	rec[index++] = y;
}

void forward(int *x, int *y, int dir)
{
	// 생쥐를 한칸 앞으로 이동
	gotoxy(*x + 1, *y + 1);
문제발생 --->	putch('');

	*x = (dir == LEFT)	? --(*x) :
		(dir == RIGHT)	? ++(*x) : *x;
	*y = (dir == UP)	? --(*y) :
		(dir == DOWN)	? ++(*y) : *y;

	record(*x , *y);	// 생쥐의 이동 경로 저장
	gotoxy(*x + 1, *y +1);
	putch(ROBOT);
}

void right(int *dir)
{
	// 생쥐의 방향을 시계방향으로 
	*dir <<= 1;
	*dir = (*dir > LEFT) ? UP : *dir;
}

void left(int *dir)
{
	// 생쥐의 방향을 반시계 방향으로
	*dir >>= 1;
	*dir = (*dir == 0) ? LEFT : *dir;
}

int still_in_maze(int x, int y)
{
	// 아직 미로에 들어 있는가 ? 
	if (x > 0 && x<MAZE_SIZE - 1 && y > 0 && y<MAZE_SIZE -1)
		return 1;
	else
		return 0;
}

int wall_ahead(int m[][MAZE_SIZE], int x, int y, int dir)
{
	//벽이 앞에 있는가 ?
	x = (dir == LEFT)	?	--x :
		(dir == RIGHT)	?	++x : x;
	y = (dir == UP)		?	--y :
		(dir == DOWN)	?	++y : y;
	return m[y][x];
}

void right_hand (int m[] [MAZE_SIZE], int x, int y, int dir)
{
	// 우선법 알고리즘
	gotoxy(x + 1, y +1);
	putch(ROBOT);
	record(x,y);

	forward(&x, &y, dir);
	while (still_in_maze(x,y))
	{
   문제 발생 -->		delay(100);
		right (&dir);
		while (wall_ahead(m, x, y, dir))
			left(&dir);
		forward(&x, &y, dir);
	}
	record(-1,-1);			// 생쥐의 움직임
	}

void del_path(int i, int j)
{
	//중복된 경로의 삭제
	while ( rec[j] >=0 )
		rec[i++] = rec[j++];
	rec[i] = -1;
}

void shortest_path(void)
{
	// 중복된 경로 제거 알고리즘 
	int i = 0;
	int x, y;
	int j;
	int x1, y1;

	while (rec[i] >=0)
	{
		x = rec[i];
		y = rec[i + 1];
		j = i + 2;
		while (rec[j] >= 0)
		{
			x1 = rec[j];
			y1 = rec[j + 1];
			if (x == x1 && y == y1)
				 del_path(i, j);
			j++;
			j++;
		}
		i++;
		i++;
	}
	i = 0;		//최단 경로를 움직이는 생쥐 애니메이션

	while (rec[i] >=0)
	{
		x = rec[i++];
		y = rec[i++];
		gotoxy(x +1, y +1);
		putch(ROBOT);
   문제발생 -->		delay(100);
		gotoxy (x + 1, y + 1);
		putch(' ');
	}
}

                       // 모든 함수의 소스를 분석할때는 MAIN()부터 본다는거 다 아시죠?  
void main(void)
{
	rec = (int*)malloc(MAZE_SIZE * MAZE_SIZE);		//생쥐의 움직임 저장
                       // 동적 메모리 할당  무슨 뜻인고 하니 , 몰라.  농담이고,....ㅋㅋ
                       // 위로 올라가 보면, rec는 int형으로 전역변수로 선언된 포인터다. 미로의 크기만큼의 (12 * 12)의 메모리를 
                       // 확보해서 rec로 넣는다. 여기서 malloc함수가 int형인것은 rec가 int형이기 때문이다.
                        
	if (rec == NULL)		//메모리 활당 에러 , 메모리 활당이 성공했는가에 대한 확인.. 왜 ? 기계는 사람이 아니므로.. 공식이다. 왜어야 한다. 
	{
		printf("\r\n Memory allocation error ! ");              // 참 보기 힘든 확장 문자가 나왔네요. '\n' 은 누구나 다 알듯이 개행 문자 , '\r'? 커스를 줄의 처음으로 이동 (ASCII : 13)
    		exit(1);                      // exit (1) 프로그램 강제 종료 
	}
	draw_maze(maze);                 // draw_maze()함수 호출 인자는 당근 ()에 들어있는 변수를 말하죠. 여기서 인자 (maze)는 뭘까요?
                                     // 위에 초기화된 배열 변수 int maze [19행] [19열]의 배열 명이죠. 배열의 대해서 모른다고 
                                     //또 책 뒤비지 말고 그렇구나 하고 끝까지 프로그램을 해석해 보세요. 그라고 나서 찾아도 안 늦어요.ㅋㅋ
                                     // 자 , 그럼 지역 함수 draw_maze()로 올라가 봅시다.                           
	
	gotoxy(40 , 5);
	printf("simulation of Micro Mouse");
	
	gotoxy(40 , 10);
	printf("press ay key to start");
	bioskey(0);
	right_hand(maze, sx, sy, LEFT);		//생쥐 1차시도

	gotoxy(40, 10);
	printf("Press any key to see shortest path");
	bioskey(0);
	shortest_path(); // 생쥐 2차 쉬도 최단경로

	gotoxy(40,10);
	printf("press any key to end program....");
	bioskey(0);
}