A mouse in the Maze : 미로찾기

//=========================================================
// 날짜 : 2005. 6. 18
// File : maze.h
//=========================================================

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXX 13
#define MAXY 17

int maze[MAXX][MAXY] =
{
 {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
 {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
 {1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
 {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
 {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
 {1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
 {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
 {1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},
 {1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1},
 {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},
 {1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
 {1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
 {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};

int mark[MAXX][MAXY] =
{
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
};
 
 //최종 경로 표시용
int good_way[MAXX][MAXY] =
{
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
};

struct MovePosition
{
 int x;
 int y;
}  mp[8] = {
 {-1,0},{-1,1},
 {0,1},{1,1},
 {1,0},{1,-1},
 {0,-1},{-1,-1}
};

class RAT;
class ListofStack;

class Node
{
 private:
  int RatPositionX;
  int RatPositionY;
  int RatDirection;
  Node *next;

 public:
  friend class ListofStack; //프렌드 선언으로 코드가 간단해진다
  friend class RAT;
  Node();
  Node(int X, int Y, int D);
  ~Node();
};

Node::Node()
{
 // 변수 초기화
 RatPositionX = -1;
 RatPositionY = -1;
 RatDirection = -1;
 next = NULL;
}

Node::Node(int X, int Y, int D)
{
 RatPositionX = X;
 RatPositionY = Y;
 RatDirection = D;
 next = NULL;
}

Node::~Node()
{ /* Do nothing */ }

class ListofStack
{
 private:
  Node *top;

 public:
  friend class RAT;
  ListofStack();
  ~ListofStack();
  Node* pop();
  Node* get_last();
  void push(Node *input_node);
  bool IsEmpty();
};

ListofStack::ListofStack()
{
 top = new Node(); //더미 노드
 top->next = NULL;
}

ListofStack::~ListofStack()
{ /* Do nothing */ }

Node* ListofStack::pop()
{
 Node *temp;
 Node *here;
 Node *before;

 if (top -> next)
 {
  before = top;
  here = top->next;
  while(here->next)
  {
   before = before ->next;
   here = here->next;
  }

  temp = here;
  before->next = NULL;
 }
 else
 {
  cout << "The stack is EMPTY\n";
  temp = NULL;
 }

 return temp;
}

Node* ListofStack::get_last()
{
 Node *temp;
 Node *here;
 Node *before;

 if (top -> next)
 {
  before = top;
  here = top->next;
  while(here->next)
  {
   before = before ->next;
   here = here->next;
  }

  temp = here;
 }
 else
 {
  cout << "The stack is EMPTY\n";
  temp = NULL;
 }
 return temp;
}

void ListofStack::push(Node *input_node)
{
 Node *here;
 Node *temp;

 temp = new Node(input_node->RatPositionX, input_node->RatPositionY, input_node->RatDirection);
 here = top;
 while(here->next)
  here = here->next;

 here->next = temp;

}

bool ListofStack::IsEmpty()
{
 if (top->next)
  return false;
 else
  return true;
}

class RAT
{
 private:
  ListofStack path;
  Node *next_move;
  char buf[80]; //input buffer

 public:
  RAT();
  ~RAT();
  int find_way();
  void display_maze(void);
  void display_mark(void);
};

RAT::RAT()
{
 //initialization
 Node *first_one = new Node(0, 0, -1);
 path.push(first_one);
 
}

RAT::~RAT()
{ /*do nothing */ }

int RAT::find_way()   //길찾기 : 실질적 메인함수
{
 Node *current_position;
 int p_i, p_j, p_d;
 p_d = -1;
 bool poped = true;
 
 while (!path.IsEmpty()) //스택이 비면 길찾기 실패
 {
  display_mark();
  gets(buf);

  if (poped) // 막힌 길을 다시 찾아가는 중이라면
  {
   current_position = path.pop();
   p_d = -1;
  }
  else  //처음 가는 길이라면
  {
   current_position = path.get_last();
   p_d = -1;
  }

  while(p_d < 8)
  {
   //current_position->RatDirection++;
   p_d++; //다음 방향을 탐색
   
   //calculate next position
   p_i = current_position->RatPositionX + mp[p_d].x;
   p_j = current_position->RatPositionY + mp[p_d].y;
   
   //미궁을 벗어나는 경우
   if (p_i < 0 || p_j < 0)
   {
    //Do nothing
   }
   //출구를 찾은 경우
   else if (p_i == 11 && p_j == 15)
   {
    cout <<"Success : I find the right way ^-^ \n";
    mark[p_i][p_j] = 1;
    next_move = new Node();
    next_move->RatPositionX = p_i;
    next_move->RatPositionY = p_j;
    next_move->RatDirection = p_d;
    path.push(next_move);
    return 1;
   }
   //처음 가는 길인 경우
   else if (maze[p_i][p_j] == 0 && mark[p_i][p_j] == 0)
   {
    mark[p_i][p_j] = 1;
    next_move = new Node();
    next_move->RatPositionX = p_i;
    next_move->RatPositionY = p_j;
    next_move->RatDirection = p_d;
    path.push(next_move);
    poped = false;
    break;
   
   }
   //8방향을 모두 탐색한 경우
   else if (p_d == 8)
    poped = true;
  }

 }
 
 //길찾기에 실패하여 빠져나온 경우
 cout << "No way out!!!\n";
 exit(0);
 
 return 0;
}

void RAT::display_maze(void) //최종 경로 표시
{
 int loop, loop2;
 Node *temp;
 while(!path.IsEmpty()) //올바른 길을 표시
 {
  temp = path.pop();
  good_way[temp->RatPositionX][temp->RatPositionY] = 1;
 }

 for (loop = 0; loop < MAXX ; loop ++)
 {
  for (loop2 = 0; loop2 < MAXY; loop2++)
  {
   if (good_way[loop][loop2])
    cout << good_way[loop][loop2];
   else
    cout << " ";
  }
  cout << endl;
 }
} //End of display_maze

void RAT::display_mark(void) //길을 찾는 과정에서의 경로 표시
{
 int loop, loop2;
 system("cls");

 for (loop = 0; loop < MAXX ; loop ++)
 {
  for (loop2 = 0; loop2 < MAXY; loop2++)
  {
   cout << mark[loop][loop2];
  }
  cout << endl;
 }
} //End of display_mark

//=========================================================
// 날짜 : 2005. 6. 18
// File : maze.cpp
//=========================================================

#include "Maze.h"

int move(void);

//Global Variables
ListofStack path; //전체 프로젝트를 관리하는 클래스

int main()
{
 
 RAT rat;
 if (rat.find_way())   //길찾기에 성공하면
  rat.display_maze();  //정확한 길을 단번에 보여준다.

 return 0;
} //End of Main