글 읽기 - 음.. 22프로에서 페일인데 어디 부분이 틀렸을까요??(주석 있음)

kioio5 7년 전 0

간단하게 설명해드리자면..

input에서 L을 받고 바로 line_input()으로

맵의 끝선 4개와

0,0세로 선을 추가해줍니다.

내가 지나간 길은 선분으로 만들어서 세로면 세로, 가로면 가로 garo, sero 벡터에 각각 저장합니다.

프로세스 함수는 solve()이며 inspect함수는 뱀이 죽을지 안죽을지를 결정합니다.

move()함수는 다음 움직일 방향을 리턴해줍니다.

고수님들의 간절한 도움이 필요합니다..

@kdk8361 님이 댓글에 달아주신 반례 안됩니다..

8
11
1 L
4 R
1 R
8 L
1 L
8 R
1 R
8 L
1 L
6 L
10 R

43이 나오는군요...

로직자체가 틀렸을까요..

#include <cstdio>
#include <iostream>
#include <vector>

#define MAX_SIZE 1010
#define ll long long

using namespace std;

typedef struct _pos
{
    int x;
    int y;
} P;

typedef struct _ti
{
    int t;
    bool direct;//0은 왼쪽 1은 오른쪽
} ti;

typedef struct _rec
{
    P st;
    P ed;
} R; // 선분 만들떄 사용 시작점 끝점으로 

vector<R> garo;
vector<R> sero;
ti data[MAX_SIZE];

int L;
int N;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
P die_point;

int abs(int a)
{
    if(a >= 0) return a;
    else return -a;
}


void line_init()
{
    int a = L + 1;

    //가로 위 아래 선 넣기
    garo.push_back(R{P{-a, a}, P{a, a}});
    garo.push_back(R{P{-a, -a}, P{a, -a}});

    //세로 왼 오른 선 넣고 0,0 넣기
    sero.push_back(R{P{-a, -a}, P{-a, a}});
    sero.push_back(R{P{a, -a}, P{a, a}});
    sero.push_back(R{P{0, 0}, P{0, 0}});
}

void input()
{
    scanf("%d %d", &L, &N);
    line_init();
    for(int i = 0; i < N; i++)
    {
        int t;
        char d;

        scanf("%d %c", &t, &d);

        data[i].t = t;
        if(d == 'L') data[i].direct = 0;
        else data[i].direct = 1;
    }

    data[N].t = 1;
}

int move(int d, bool d2)//d는 동서남북 d2는 왼쪾 오른쪾
{
    switch(d)
    {
    case 0:// 위
        if(d2 == 0) return 2;
        else return 3;
        break;
    case 1://아래
        if(d2 == 0) return 3;
        else return 2;
        break;
    case 2://왼
        if(d2 == 0) return 1;
        else return 0;
        break;
    case 3://오
        if(d2 == 0) return 0;
        else return 1;
        break;
    }
}

bool inspect(P sp, P ep, int d) //선분의 시작점, 끝점, 방향
{
    bool die = 0;
    bool swap_flag = 0;

    if(d == 0 || d == 1) // 위 아래
    {
        for(int i = 0; i < garo.size(); i++) // 가로 선분 백터 검사
        {
            if(ep.x < garo[i].st.x || ep.x > garo[i].ed.x) continue;
            //만약 가로 선분 x범위를 벗어나면 컨티뉴

            if(sp.y > ep.y) // 시작점 y값이 끝점 y보다 크면 스왑해주고
            {
                swap(sp, ep);
                swap_flag = 1; // 플래그를 1로만든다.
            }

            if(garo[i].ed.y >= sp.y && garo[i].ed.y <= ep.y) // 만약 선분안에 포함되면
            {
                die_point = P{sp.x, garo[i].ed.y}; // 죽은 포인트를 저장하고.
                if(swap_flag == 0 && sp.x == die_point.x && sp.y == die_point.y) continue;
                if(swap_flag == 1 && ep.x == die_point.x && ep.y == die_point.y) continue;
                //만약 죽은포인트가 방금 출발한 지점이라면 컨티뉴해준다.
                //방금전에 만들어진 선분이 걸리기 때문에..

                die = 1; // 그것이 아니라면 다이를 1로해주고 브레이크
                break;
            }
        }
    }
    else // 마찬가지
    {
        for(int i = 0; i < sero.size(); i++)
        {
            if(ep.y < sero[i].st.y || ep.y > sero[i].ed.y) continue;

            if(sp.x > ep.x)
            {
                swap(sp, ep);
                swap_flag = 1;
            }

            if(sero[i].ed.x >= sp.x && sero[i].ed.x <= ep.x)
            {
                die_point = P{sero[i].ed.x, sp.y};
                if(swap_flag == 0 && sp.x == die_point.x && sp.y == die_point.y) continue;
                if(swap_flag == 1 && ep.x == die_point.x && ep.y == die_point.y) continue;

                die = 1;
                break;
            }
        }
    }
    return die;
}

void add_line(P sp, P ep, int d)
{
    if(d == 0 || d == 1)//세로 선분 추가
    {
        if(sp.y > ep.y) swap(sp, ep);
        sero.push_back(R{sp, ep});
    }
    else// 가로 선분 추가
    {
        if(sp.x > ep.x) swap(sp, ep);
        garo.push_back(R{sp, ep});
    }
}

ll solve()
{
    int d = 3;
    ll sec = 0;
    bool die = 0;
    int idx = 0;

    P sp = P{0, 0};//시작점
    P ep = P{0, 0};//도착점

    while(1)
    {
        ep.x += dx[d] * data[idx].t;//방향과 시간을 곱해서 위치를 정해줌
        ep.y += dy[d] * data[idx].t;

        sec += data[idx].t; // 걸린 시간만큼 더함.

        die = inspect(sp, ep, d); // 이동해서 죽엇는지 검사.

        if(die) // 죽엇다면 넘치는 만큼 뺴주고 리턴.
        {
            if(d == 0 || d == 1) sec -= abs(ep.y - die_point.y);
            else sec -= abs(ep.x - die_point.x);
            return sec;
        }

        add_line(sp, ep, d); //안죽으면 해당 선분 추가.
        sp = ep; // 시작점에다가 끝점을 저장. 끝점이 시작점이 될것이기때문.

        if(idx < N)
        {
            d = move(d, data[idx].direct);
            idx++;
        }
        //idx가 입력받은 데이터안에 있으면 위치정해줄수 잇음.
        //데이터가 끝나면 그대로 직진

//        if(idx == N) data[N].direct = d; //
//        else idx++;
    }


}

int main()
{
    input();
    printf("%lld\n", solve());

    return 0;
}

kioio5 7년 전 0

실수한 부분 찾았습니다.

가장 가까운 선분과의 차이를 뺏어야하는데

아무선분이나 만나기만하면 바로 뺴버렷네요...

kioio5 7년 전 0

해결했습니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

@kdk8361 다른 질문에 댓글 달아주신 반례 덕분에 해결했습니다!!!
감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

음.. 22프로에서 페일인데 어디 부분이 틀렸을까요??(주석 있음)

kioio5 7년 전 0

@kdk8361 님이 댓글에 달아주신 반례 안됩니다..

kioio5 7년 전 0

kioio5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말