Right Hand Rule

Maze 문제를 풀기 위해 사용할 수 있다.

1. 앞으로 간다

2. 아직 미로 안에 갖혀 있다면

    2.1 시계 방향으로 90도 돈다.

    2.2 만약 벽이 앞에 있다면 반시계 방향으로 90도 돈다.

#include <dos.h>
#include <conio.h>
#include <bios.h>
#include <stdlib.h>

#define MAZE_SIZE  19
#define ROBOT       2

int maze[MAZE_SIZE][MAZE_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 sx = MAZE_SIZE - 1, sy = MAZE_SIZE - 2;

int *rec;  /* record robot's path */

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

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, 197 };
    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]) //미로를 그림
    {
    int i, j;
    for (j = 0; j < MAZE_SIZE; j++)
        for (i = 0; i < MAZE_SIZE; i++)
            {
            gotoxy(i + 1, j + 1); //gotoxy() 를 이용하는 경우, 좌측 상단이 (0,0) 이 아니라 (1,1) 이기 때문
            putch(get_shape(m, i, j));
            }
    }

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) //오른쪽으로 90도 방향 전환
    {
    *dir <<= 1;
    *dir = (*dir > LEFT) ? UP : *dir;
    }

void left(int *dir) //왼쪽으로 90도 방향 전환
    {
    *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);  /* end of path */
    }

int del_path(int i, int j) //중복되는 경로 (i ~ (j-1) 사이) 를 제거
    {
    int k = i;
    while (rec[j] >= 0) // j ~ 마지막 좌표까지 값을 , i ~ 에다가 overwrite
        rec[i++] = rec[j++];
    rec[i] = -1; //마지막 좌표 다시 표시
    return k;   /* k is j position after deleting */ //현재 index 위치 다시 리턴
    }

void shortest_path(void) // right_hand() 를 통해 저장된 경로 중, 중복되는 경로를 제거하여 최단경로 찾아냄
    {
    int i = 0;
    int x, y;
    int j;
    int x1, y1;

    while (rec[i] >= 0) //마지막 좌표(-1, -1)가 아닌 경우
        {
        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) //현재 좌표와 같이 같은 좌표가 있으면, 중복 경로 삭제
                j = del_path(i, j);

            j = j + 2; //다음 좌표
            }

        i = i + 2; //다음 좌표
        }
    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(' ');
        }
    }


void main(void)
    {
    rec = (int*)malloc(MAZE_SIZE * MAZE_SIZE);
    if (rec == NULL)
        {
        cputs("\r\n Memory allocation error ! ");
        exit(1);
        }
    clrscr();
    draw_maze(maze);

    gotoxy(40, 5);
    cputs("Simulation of Micro Mouse");
    gotoxy(40, 10);
    cputs("  Press any key to start...");
    bioskey(0);
    right_hand(maze, sx, sy, LEFT);

    gotoxy(40, 10);
    cputs("  Press any key to see shortest path...");
    bioskey(0);
    shortest_path();

    gotoxy(40, 10);
    cputs("  Press any key to end program...      ");
    bioskey(0);
    }

* 출처 : C로 배우는 알고리즘