미궁 의 문제 를 귀착 하여 풀다

갑작스런 귀환이 미로 문제를 해결하고 귀환의 본질에 대한 인상을 깊게 했다. 처음에 STL의 set 용기를 사용했는데 stl 용기는 정렬 용기이다. 사용자 정의 대상을 불러올 때 사용자 정의 정렬 함수가 필요하고 마지막에 벡터 벡터로 저장하는 경로를 선택했는데 벡터는 대기열의 성질이 있다.
미로를 풀기 위한 귀환 절차는 네 가지 방향으로 갈 수 있는지 검사하고, 죽음의 길을 만나면 원래의 길로 귀환하여false로 돌아가고, 출구를 만나면true로 돌아가며 장래의 노선을 대열에 저장하는 것이다.

#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
int maze[10][15] = {
 {1,0,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,1},
 {1,1,1,0,1,0,1,1,0,1,1,0,1,1,1},
 {1,0,0,0,1,0,1,0,0,1,1,0,1,1,1},
 {1,0,1,1,1,0,1,1,0,1,1,0,0,0,1},
 {1,0,1,1,1,0,1,1,0,1,1,0,1,1,1},
 {1,0,0,0,0,0,1,1,0,1,0,0,1,1,1},
 {1,1,1,1,1,1,0,0,0,1,1,0,0,0,1},
 {1,1,0,0,0,0,0,1,1,0,0,0,1,1,1},
 {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1}};

#define  UP 1
#define  DOWN  2
#define  LEFT  3
#define  RIGHT 4
struct SPoint{
 int x;
 int y;
};
static int count = 0;
//struct Compare{
// bool operator() ( const SPoint& p1, const SPoint& p2) const
// {
//  if (p1.x < p2.x)
//  {
//   return true;
//  }
//  else if (p1.x == p2.x)
//  {
//   if (p1.y < p2.y)
//   {
//    return true;
//   }
//  }
//  return false;
// }
//};

bool walk(std::vector<SPoint>& routeVector, int srcDirect, SPoint nowPoint)
{
 count++;
 //  
 /*for (std::vector<SPoint>::iterator it = routeVector.begin(); it != routeVector.end(); ++it)
 {
  if ((*it).x == nowPoint.x && (*it).y == nowPoint.y)
  {
   return false;
  }
 }*/
 //  
 if (1 == nowPoint.x && 0 == nowPoint.y )
 {
  routeVector.push_back(nowPoint);
  return true;
 }
 int nowX = nowPoint.x;
 int nowY = nowPoint.y;
 SPoint nextPoint;
 bool passFlag = false;
 for(int direct = 1; direct <= 4; ++direct)
 {
  //  
  if (srcDirect == direct)
  {
   continue;
  }
  switch(direct)
  {
  case UP:
   {
    if (maze[nowY - 1][nowX] == 0)
    {
     nextPoint.x = nowX;
     nextPoint.y = nowY -1;
     if(walk(routeVector, DOWN, nextPoint))
     {
      passFlag = true;
     }
    }
    break;
   }
  case DOWN:
   {
    if (maze[nowY + 1][nowX] == 0)
    {
     nextPoint.x = nowX;
     nextPoint.y = nowY +1;
     if(walk(routeVector, UP, nextPoint))
     {
      passFlag = true;
     }
    } 
    break;
   }
  case LEFT:
   {
    if (maze[nowY][nowX - 1] == 0)
    {
     nextPoint.x = nowX - 1;
     nextPoint.y = nowY;
     if(walk(routeVector, RIGHT, nextPoint))
     {
      passFlag = true;
     }
    } 
    break;
   }
  case RIGHT:
   {
    if (maze[nowY][nowX + 1] == 0)
    {
     nextPoint.x = nowX + 1;
     nextPoint.y = nowY;
     if(walk(routeVector, LEFT, nextPoint))
     {
      passFlag = true;
     }
    } 
    break;
   }
  default:
   break;
  }
 }
 if (passFlag)
 {
  routeVector.push_back(nowPoint);
 }
 return passFlag;
}
void print_maze()
{
 for (int raw = 0; raw < 10; ++raw)
 {
  for (int column = 0; column < 15; ++column)
  {
   if (maze[raw][column] == 1)
   {
    printf("■");
   }
   else if(maze[raw][column] == 2)
   {
    printf("★");
   }
   else
   {
    printf("  ");
   }
 
   if (column == 14)
   {
    printf("
");
   }
  }
 }
}
void paving(std::vector<SPoint> routeVec)
{
 for (std::vector<SPoint>::iterator it = routeVec.begin(); it != routeVec.end(); ++it)
 {
  int raw = (*it).y;
  int column = (*it).x;
  maze[raw][column] = 2;
 }
}
int main(int argc, char* argv[])
{
 for (int i = 0; i < argc; ++i)
 {
  printf(" : %s 
", argv[i]);
 }
 SPoint point;
 point.x = 9;
 point.y = 9;
 SPoint nextPoint;
 nextPoint.x = 9;
 nextPoint.y = 8;
 std::vector<SPoint> routeVec;
 walk(routeVec, DOWN, nextPoint);
 routeVec.push_back(point);
 paving(routeVec);
 print_maze();
 printf(" : %d", count);
 while(true);
}