미로에 갖힌 생쥐 문제 (Maze mouse)

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<windows.h> 

#define MAX_SIZE 19
#define ROBOT1   38   // & 

#define UP      1  
#define RIGHT   2
#define DOWN    4
#define LEFT    8 

int get_shape(int, int);
void draw_maze(void);
void gotoxy(int , int);
void right_hand(int, int, int);
int wall_ahead(int, int, int);
void right(int*);
void left(int*);
int still_in_maze(int, int);
void foward(int*, int*, int);
void shortest_path(void);
void del_path(int, int);
void record(int, int);

int maze[MAX_SIZE][MAX_SIZE]={
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {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* save;  // 이동경로 저장

void main()
{
    save = (int*)malloc(MAX_SIZE * MAX_SIZE);  // 배열 생성
    if(save==NULL)
    {
        printf("Memory allocation error !!!!\n");
        exit(1);
    }
    draw_maze();  // 미로 그리는 함수 호출
    gotoxy(40, 5);
    cputs("Simulation of Micro Mouse");
    gotoxy(40, 10);
    cputs("\t Press any key to start...");
    getche();

    right_hand(MAX_SIZE-2, MAX_SIZE-1, LEFT);  // 미로 이동 실행   
    gotoxy(40, 10);
    cputs("\t Press any key to see shortest path...");
    getche();

    shortest_path();  // 최단거리 함수 호출
    gotoxy(40, 20);
} 

// 최단거리 함수 출력
void shortest_path(void)
{
    int init_x, init_y;
    int i, j;  
    for(i=0 ; save[i]>-1 ; i++)
    {
        init_x = save[i++];
        init_y = save[i];
        for(j=i+1 ; save[j]>-1 ; j++)
        {
            if(save[j++] == init_x && save[j] == init_y)
                del_path(i-1, j-1);
        }
    }

    // 출력
    i=0;
    while(save[i]>-1)
    {
        gotoxy(save[i+1]+1, save[i]+1);
        putchar(ROBOT1);
        Sleep(100);
        gotoxy(save[i+1]+1, save[i]+1);
        putchar(' ');
        i+=2;
    }
} 

// 필요없는 경로 삭제 함수
void del_path(int x, int y)
{
    int i;
    for(i=0; save[y+i]>-1 ; i++)
        save[x+i] = save[y+i];
    save[x+i] = -1; // 배열의 끝을 선언
}

 // 이동경로 저장 함수
void record(int x, int y)
{
    static int i = 0;
    save[i++] = x;
    save[i++] = y;
} 

// 미로 이동 함수
void right_hand(int x, int y, int dir)
{
    gotoxy(y + 1, x + 1);
    putchar(ROBOT1);
    Sleep(100);
    record(x, y);

    foward(&x, &y, dir);
    while(still_in_maze(x, y))
    {
        right(&dir);
        while(wall_ahead(x, y, dir)) // 앞에 벽이 1이 없을때 까지
        {          
            left(&dir);
        }
        foward(&x, &y, dir);
    }
    record(-1, -1); // 배열 마지막을 선언
} 

//다음 경로값 1 확인 함수
int wall_ahead(int x, int y, int dir)
{
    switch(dir)
    {
        case UP     : --x; break;
        case RIGHT  : ++y; break;
        case DOWN   : ++x; break;
        case LEFT   : --y; break;
    }
    return maze[x][y];
} 

// 오른쪽으로 회전
void right(int* dir)
{
    *dir = *dir << 1;
    if((*dir) > LEFT)
        *dir = UP;
}

//왼쪽으로 회전
void left(int* dir)
{
    *dir = *dir >> 1;
    if((*dir) < UP)
        *dir = LEFT;
}

//미로 안에 있는지 판별 함수
int still_in_maze(int x, int y)
{
    if(x>0 && x< MAX_SIZE-1 && y>0 && y<MAX_SIZE-1)
        return 1;
    else
        return 0;
}

//방향에 따라 전진 하는 함수
void foward(int* x, int* y, int dir)
{
    gotoxy((*y)+1, (*x)+1);
    putchar(' ');

    switch(dir)
    {
        case UP     : --(*x); break;
        case RIGHT  : ++(*y); break;
        case DOWN   : ++(*x); break;
        case LEFT   : --(*y); break;
    }
    gotoxy((*y)+1, (*x)+1);
    putchar(ROBOT1);
    Sleep(100);
    record(*x, *y);
} 

// 미로글 그리는 함수
void draw_maze(void)
{
    int i, j;

    for(i=0 ; i<MAX_SIZE ; i++)
        for(j=0 ; j<MAX_SIZE ; j++)
        {
            gotoxy(j+1 , i+1);
            putchar(get_shape(i ,j));
        }
}

 //미로의 값에 따라 형태를 리턴하는 함수
int get_shape(int x, int y)
{
    static int shape[]= { 32, 5, 6, 3, 5, 5, 1, 25, 6, 4, 6, 21, 2, 23, 22, 16};
    int s=0;

    if(maze[x][y])
    {
        if(x>0 && maze[x-1][y])
            s = s | UP;
        if(x<MAX_SIZE-1 && maze[x+1][y])
            s = s | DOWN;
        if(y>0 && maze[x][y-1])
            s = s | LEFT;
        if(y<MAX_SIZE-1 && maze[x][y+1])
            s = s | RIGHT;
    }

    return shape[s];
}

 //VC 6.0 에서 사용할수 없는 gotoxy()함수 구현
void gotoxy(int x, int y)
{
    COORD Pos = {x-1,y-1};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),Pos);
}