BRAVEDUCK문제 도저히 못풀겠슴

  • cjkis
    cjkis

    http://algospot.com/judge/problem/read/BRAVEDUCK

    #include <iostream>
#include <algorithm>
#include <list>

using namespace std;

struct DeleteObject
{
    template<typename T>
    void operator () (const T* ptr) const
    {
        delete ptr;
    }
};

class Point
{
public:
    int x;
    int y;
    Point(){}
    Point(int x,int y):x(x),y(y){}
};

Point* pGoal;
Point* pStart;
list<Point*> stones;
int squareJump;

inline int GetSquareDistance(const Point* p1, const Point* p2)
{
    int dx=p1->x-p2->x;
    int dy=p1->y-p2->y;
    return dx*dx + dy*dy;
}

inline bool CanJump(const Point* pPos1, const Point* pPos2)
{
    return GetSquareDistance(pPos1, pPos2) <= squareJump;
}

bool CompareStart(const Point* pPos1, const Point* pPos2)
{
    return GetSquareDistance(pPos1, pStart) < GetSquareDistance(pPos2, pStart);
}

bool CompareGoal(const Point* pPos1, const Point* pPos2)
{
    return GetSquareDistance(pPos1, pGoal) < GetSquareDistance(pPos2, pGoal);
}

void GetJumpableStones(list<Point*>& jumpableStones, list<Point*>::iterator nowIter)
{
    list<Point*>::iterator startIter=nowIter;
    list<Point*>::iterator endIter=++startIter;

    for(list<Point*>::reverse_iterator reverseIter(nowIter);
        reverseIter!=stones.rend(); reverseIter++)
    {
        if(*reverseIter == *nowIter) continue;
        if(CanJump(*nowIter, *reverseIter))
        {
            startIter=(++reverseIter).base();
        }
        else
        {
            break;
        }
    }

    for(list<Point*>::iterator iter=nowIter; iter!=stones.end(); iter++)
    {
        if(*iter == *nowIter) continue;
        if(CanJump(*nowIter, *iter))
        {
            endIter=iter;
        }
        else
        {
            break;
        }
    }

    jumpableStones.insert(jumpableStones.begin(), startIter, ++endIter);
    //jumpableStones.reverse();
    //jumpableStones.sort(&CompareGoal);
}

bool JumpGoal(Point* nowPos)
{
    if(CanJump(nowPos, pGoal))
    {
        return true;
    }
    else
    {
        list<Point*>::iterator nowIter=find(stones.begin(), stones.end(), nowPos);
        list<Point*> jumpableStones;
        GetJumpableStones(jumpableStones, nowIter);
        list<Point*>::iterator oldIter=nowIter;
        if(oldIter!=stones.begin())
            --oldIter;
        stones.erase(nowIter);
        for(list<Point*>::iterator iter=jumpableStones.begin(); iter!=jumpableStones.end(); iter++)
        {

            if(JumpGoal(*iter))
            {
                return true;
            }
        }
        stones.insert(oldIter, nowPos);
        return false;
    }
}

void RunGame()
{
    int stoneCount,x,y;
    cin>>squareJump;
    squareJump=squareJump*squareJump;
    cin>>x>>y;
    pStart=new Point(x,y);
    cin>>x>>y;
    pGoal=new Point(x,y);
    cin>>stoneCount;
    stones.push_back(pStart);
    for(int i=0; i<stoneCount; i++)
    {
        cin>>x>>y;
        stones.push_back(new Point(x,y));
    }
    stones.sort(&CompareStart);
    if(JumpGoal(pStart))
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    for_each(stones.begin(), stones.end(), DeleteObject());
    stones.erase(stones.begin(), stones.end());
    delete pGoal;
}

int main(int argc, char *argv[])
{
    int gameCount;
    cin>>gameCount;
    for(int i=0; i<gameCount; i++)
    {
        RunGame();
    }
    return 0;
}

    ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

    오류를 잡아달라는게아님
    아무리 개지랄을 해도 시간초과 or 오답입

    제발 답점 알려주셈


    11년 전
17개의 댓글이 있습니다.
  • Being
    Being

    질문과 답변 게시판에 글을 쓰실 때, 혹 글 쓰는 요령에 대한 도움말이 나오지 않던가요?


    11년 전 link
  • Kureyo
    Kureyo

    완전히 제대로 질문을 해달라는게 아님
    소스코드도 엉망이고 말투도 디씨체임
    제발 글좀 제대로 써주셈


    11년 전 link
  • cjkis
    cjkis

    글이란 의미만 전달되면 되는것이 아니겠소? 공자께서 말씀하시길 그 형식보단 마음가짐이 더 중요하다 하였소 허허 나의 마음을 이해하시고 어서 나를 답의 길로 인도해주길 바라오


    11년 전 link
  • JongMan
    JongMan

    진실된 마음을 논하시기 전에 문제에 나와 있는 예제부터 돌려보고 오심이...


    11년 전 link
  • Being
    Being

    질문자님 예전 코드들을 전에 가볍게 본 적이 있는데, 초반에 제출하셨던게 그나마 풀이로 갈 가능성이 가장 크지 않나 그렇게 생각합니다. 문제는 질문자님께서 너무 나이브하게 탐색을 하다 보니 조합 폭발을 겪고 있다는 점이죠.


    11년 전 link
  • cjkis
    cjkis

    Being님 제발 답점 알려주셈 난이제 틀렸씀 소스코드좀 나에게 보내주샘 ㅠㅠ cjkis@naver.com
    답을보고 분석하는게 빠를듯 내가 몇주간 이거때문에 시간만 날리고 나의 수양을 하지 못했슴 더이상 벽에대고 삽질을 하고싶지 않음


    11년 전 link
  • cjkis
    cjkis

    처음에 돌려본문제는 아무리 개조해봐야 시간초과가 나오더군요 시간초과를 없애려다보니 막장탐색이 되었슴 으헤헤헤헤ㅔㅎ


    11년 전 link
  • Being
    Being

    시간을 날렸다고 생각하실 게 아니라 갈 길이 멀다는 걸 느낀 소중한 몇 주였다고 생각하시는건 어떨까요? 아니면 차라리 여기 포탈 쏴준 프갤 분들께 질문하시던지요 ㅎㅎ 행운을 빕니다. :)


    11년 전 link
  • JongMan
    JongMan

    깊이 우선 탐색 혹은 너비 우선 탐색을 해보세요.


    11년 전 link
  • cjkis
    cjkis

    ㅎㅎ 프갤인지 어찌암? 프갤놈들 잘 모르르듯 ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ 제발 알고형님 답점 나 빨리 Effective C++보고 C++고수되야되는데 3주간 이거푸느냐고 책한자도 못봤음


    11년 전 link
  • JongMan
    JongMan

    알고스팟 운영 정책상 솔루션 코드나 채점 데이터는 공개하지 않습니다. 따라서 여러번 요청하셔도 보내드리진 못합니다. :-) 작성하신 코드들을 보니 프로그래밍을 못하시는 것도 아니니, 문제 하나만 고치면 쉽게 푸실 수 있을 거라고 생각됩니다.

    지금 cjkis님 코드의 최대 문제는 n!개의 모든 경로를 다 검색한다는 것입니다. 만약 답이 없을 경우 엄청나게 많은 경로를 모두 찾게 됩니다. 하지만 모든 경로를 다 만들어 볼 필요는 없습니다. 시작점에서 점프해서 갈 수 있는 돌과, 갈 수 없는 돌로 돌들을 나눈다고 생각해 보시면 문제가 간단해질 것 같습니다.

    그리고 가능하면 디씨체는 자제해 주시면 감사하겠습니다.


    11년 전 link
  • Kureyo
    Kureyo

    초반방법이 가장 좋았음 타임아웃막는법은 중복체크를 잘해보면됨 좀더고민해보셈 이정도면 알려준거나 마찬가지임 ㅇㅋ?


    11년 전 link
  • cjkis
    cjkis

    풀었다능 우헤헤헤헤헤,,,,,,,,,,, 벡터에 Point대신 Point*넣으니깐 빨라진것 같아염


    11년 전 link
  • cjkis
    cjkis

    또한 여러분님들의 말대로 첫번째 코드를 좀 수정했다능 이 모든게 여러분들의 덕이 아니겠소? 우헤헤헤헤


    11년 전 link
  • cjkis
    cjkis

    그리고 한번갔던곳을 지울필요가 없었음.. 히스토리를 지운게 패인이었슴


    11년 전 link
  • Being
    Being

    벡터에 포인트 넣은 건 차이는 있지만 아주 드라마틱한 변화는 아니었을 겁니다. 관건은 방금 말씀하신 부분이죠. 탐색 횟수를 조사해 보시면 좋은 경험이 될 것 같네요.


    11년 전 link
  • Being
    Being

    포인터*


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.