Prob No.02D8 : Perimeter [CH03.3.USACO(Silver)]

Prob No.02D8 : Perimeter [CH03.3.USACO(Silver)]
http://koistudy.net/?mid=prob_page&NO=728

이 문제에 대한 풀이는 정말 쉽다. 건초의 위치를 set으로만 표현해주면 풀 수 있다.
일단 set을 일차원 배열로 잡는다.
set<int> S[1000010];
y,x를 입력 받으면
S[y].insert(x)를 해준다.
어떤 좌표 y,x에 건초가 있는지 없는지는 log n 만에 알 수 있다.
​
세가지 데이터를 가지고 진행하면 된다.
현재 y,x,방향
가장 왼쪽 중 가장 높을 곳을 시작 시점으로 하고  방향은 위를 가르킨다. 이곳이 가장자리임은 분명하다.


현재 위치에 대하여 현재 방향으로 한칸 간 칸을 A라 하고
 한칸 간 칸에 대해 왼쪽으로 90도 돌아 있는 칸을 B라하자


if B에 건초가 있을 때
B위치로 이동, 방향 왼쪽 90도 회전
else
    if A에 건초가 있을 때
        A위치로 이동, 방향 유지
   else
       현재 위치 유지, 방향 오른쪽 90도 회전


처음 위치과 방향으로 돌아 올때 까지 이 과정을 반복한다.
총 이동 횟수가 정답이다.

perimeter code


#include <algorithm>
#include <cstdio>
#include <set>
#define INF 987654321
using namespace std;
set<int> S[1000010];
set<int>::iterator it;
int n,sy,sx,ans,dy[4]={0,1,0,-1},dx[4]={1,0,-1,0};
void input()
{
    scanf("%d",&n);
    int y,x,i;
    sy=sx=INF;
    for(i=1;i<=n;i++){
        scanf("%d %d",&y,&x);
        S[y].insert(x);
        if(sy>y){
            sy=y,sx=x;
        }
        else if(sy==y && sx>x){
            sy=y,sx=x;
        }
    }
}
void process()
{
    int y=sy,x=sx,dir=3,ty1,tx1,tx2,ty2,ck1,ck2;
    do{
        ans++;
        ty2=y+dy[dir];
        tx2=x+dx[dir];
        ty1=ty2+dy[(dir+3)%4];
        tx1=tx2+dx[(dir+3)%4];
        it=S[ty1].find(tx1);
        if(it==S[ty1].end())
            ck1=0;
        else
            ck1=1;
        it=S[ty2].find(tx2);
        if(it==S[ty2].end())
            ck2=0;
        else
            ck2=1;
        if(ck1==1){
            y=ty1;
            x=tx1;
            dir=(dir+3)%4;
        }
        else{
            if(ck2==1){
                y=ty2;
                x=tx2;
            }
            if(ck2==0){
                dir=(dir+1)%4;
            }
        }
    }while(!(y==sy && x==sx && dir==3));
    printf("%d",ans);
}
int main(){
    input();
    process();
    return 0;
}