UVA 314 로봇 이동하기(C++)

로봇 연구소에서는 매장의 어느 지점에서 다른 지점까지 이동하는 로봇을 구상하고 있다.
로봇은 트랙을 따라 이동하며, 트랙은 직사각형 모양의 매장내부에 1미터 간격의 격자무늬로 배치되어 있다.
매장의 크기는 가로 n미터 세로 m미터이고 트랙은 가게의 꼭지점부터 1미터 간격으로 설치 되어있으며 가게 모서리로는 설치되어 있지 않다.
로봇의 모양은 밑면이 반지름  0,8미터인 원통형 이다.
매장 내부에는 1mx1m크기의 장애물 들이 존재하고 장애물들은 1미터 간격의 격자무늬 안으로 배열되어있어 1미터 단위의 격자 밖으로 삐져나올 일은 없다.
로봇은 벽이나 장애물에 걸리면 그 트렉을 지나갈 수 없다.
로봇은 트랙의 교차점에서만 회전을 할 수 있고
오직 전진만 가능하다.
로봇은 1초동안 다음과 같은 행동을 하나씩 할 수 있다.
1. 1m 전진
2. 2m 전진
3. 3m 전진
4. 오른쪽 90도 회전
5.왼쪽 90도 회전

이제 로봇이 매장의 한쪽 지점에서 다른쪽 지점으로 이동하는데 가장 짧게 걸리는 시간을 구하는 프로그램을 만들어 보자.

***입력은 다음과 같다***
입력은 여러개의 테스트 데이터로 이루어진다.
m n (매장의 크기 세로와 가로(m) m,n<=50)
o o ... o
.
.
.
o o ... o(mxn크기의 매장지도 1mx1m공간을 단위로 나타내며, 1은 장애물의 위치를 나타낸다)
d1 d2 e1 e2 direction (출발점의 좌표 :매장의 북서쪽 지점으로부터 e1m 남쪽 e2m 동쪽지점/ 도착점좌표 : 북서쪽으로부터 d1m남쪽 d2m동쪽지점 / direction 시작할때 로봇의 정면방향, e1,e2,d1,d2는 정수이며 direction은 방위의 영어 소문자이다(ex, south))
이게 한개의 태스트 데이터이며 또 다른 테스트 데이터의 입력이 가능하다.
0 0이 입력되면 테스트 데이터의 끝이다.

***출력은 다음과 같다***
t(t는 도착지까지 가장 빠르게 도달하는데 걸린 시간(s), 목적지에 도달하는 경로가 없으면 -1 출력)
다음 테스트 데이터의 출력결과는 다음줄에 출력한다.




/*로봇이 할수 있는 모든 경우의 수를 BFS를 이용해 구해가면서 목적지에
도달한 순간 종료한다.
로봇이 할수있는 행동은 5가지 밖에 안된다. 1,2,3미터 전진, 좌회전 우회전*/
#include <iostream>
#include <windows.h>
#include <deque>
#include <string>
#include <memory.h>
#include <stdlib.h>
using namespace std;
enum direction {NORTH, EAST, SOUTH, WEST};
//로봇 정면방향에 따른 이동방향 설정.
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
bool wmap[51][51];//0~m,0~n까지 미터단위로 트랙이 깔리므로, 물론 모서리 트랙은 못지나간다.
bool flag[50][50][4];
int m,n,e1,e2;//가게의 세로길이와 가로 길이. 로봇의 도착좌표
deque<int> x,y,step;//로봇의 x좌표 y 좌표 명령 단계에 대한 큐 생성.
deque<direction> dir;//로봇의 정면방향에 대한 큐생성.
int bfs();
int main(){
   
    int i,j;
    bool map[50][50];//단위제곱미터당 장애물의 존재 유무
    int result=0;
    int b1,b2;//출발좌표
    string direct;//처음 정면방향
   
    while(cin>>m>>n){
                     if(n==0&&m==0)break; //종료조건
                   
                     memset(wmap,false,sizeof(wmap));//wmap 초기화
                     memset(flag,false,sizeof(flag)); //flag초기화
                    
                    
                     for(i=0;i<m;i++){
                                      for(j=0;j<n;j++){
                                                       cin>>map[i][j];
                                                       //장애물에 걸쳐있는 교차점은 모두 지나갈 수 없다.
                                                       if(map[i][j]==true){
                                                                        wmap[i][j]=true;
                                                                        wmap[i][j+1]=true;
                                                                        wmap[i+1][j]=true;
                                                                        wmap[i+1][j+1]=true;
                                                       }                
                                      }                
                     }
                   
                    
                     cin>>b1>>b2>>e1>>e2>>direct;//출발 좌표와 도착좌표 초기 정면방향을 입력받기
                    
                    
                     //큐에 초기정보를 입력
                     x.push_back(b2);
                     y.push_back(b1);
                     if(direct=="north")dir.push_back(NORTH);
                     else if(direct=="south")dir.push_back(SOUTH);
                     else if(direct=="east")dir.push_back(EAST);
                     else dir.push_back(WEST);
                     step.push_back(0);
                     //큐가 빌때 까지 반복
                     while(!y.empty()){
                                     result = bfs();//한 스탭마다 처리되는 행동
                                     if(result == 1)break;//1이 반환되면 종료
                     }
                    
                     if(y.empty())cout<<-1<<endl;//목적지에 도달 못하면 -1
                     else cout<<step.front()<<endl;
                    
                     x.clear();
                     y.clear();
                     dir.clear();
                     step.clear();
    }
    system("PAUSE");
   
    return 0;
}
int bfs(){
   
    /*현재 로봇의 위치가 장애물이나 경계선 바깥에 존재할때는 검색하지 않는다.
    */
    if(x.front()<=0||x.front()>=m||y.front()<=0||y.front()>=n||wmap[y.front()][x.front()]==true){
                                                                                              x.pop_front();
                                                                                              y.pop_front();
                                                                                              dir.pop_front();
                                                                                              step.pop_front();
                                                                                             
                                                                                              return 0;
    }
    //이미 검색한 위치일 경우 검색하지 않는다.
    if(flag[y.front()][x.front()][dir.front()]!=false){
                                                   x.pop_front();
                                                   y.pop_front();
                                                   dir.pop_front();
                                                   step.pop_front();
                                                  
                                                   return 0;
    }
    //깃발 검사를 한뒤 깃발을 꽂는다.
    flag[y.front()][x.front()][dir.front()]=true;
   
    if(x.front()==e2&&y.front()==e1){
                                     return 1;
    }
   
    //1칸 전진
    x.push_back(x.front()+dx[dir.front()]);
    y.push_back(y.front()+dy[dir.front()]);
    dir.push_back(dir.front());
    step.push_back(step.front()+1);
    //2칸 전진
    x.push_back(x.front()+dx[dir.front()]*2);
    y.push_back(y.front()+dy[dir.front()]*2);
    dir.push_back(dir.front());
    step.push_back(step.front()+1);
    //3칸 전진
    //중간에 장애물을 그냥 지나치는지 검사하기 위해 다음과 같은 방법을 쓰겠다
    //중간에 장애물이 있는지 한칸만 검사해본다. 나머지는 다음번에 검사 가능하다.
    if(wmap[y.front()+dy[dir.front()]][x.front()+dx[dir.front()]]!=true){
                                                                         x.push_back(x.front()+dx[dir.front()]*3);
                                                                         y.push_back(y.front()+dy[dir.front()]*3);
                                                                         dir.push_back(dir.front());
                                                                         step.push_back(step.front()+1);
    }
    //오른쪽 회전
    x.push_back(x.front());
    y.push_back(y.front());
    dir.push_back(direction((dir.front()+1)%4));
    step.push_back(step.front()+1);
    //왼쪽 회전
    x.push_back(x.front());
    y.push_back(y.front());
    dir.push_back(direction((dir.front()+3)%4));// 음수에서는 나머지가 -로 나오므로 -1대신 +3을 쓴다.
    step.push_back(step.front()+1);
   
    x.pop_front();
    y.pop_front();
    dir.pop_front();
    step.pop_front();
   
   
    return 0;
}


실행결과
10 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
9 1 1 9 west
10