글 읽기 - 구슬 탈출 틀린 예시를 모르겠네요

homs44 5년 전 0

BFS로 풀었는데 혹 잘못된건가요??

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

enum DIRECTION {NONE,TOP,BOTTOM,RIGHT,LEFT};

class Ball{
public:
    int x;
    int y;
    Ball(){
        
    }
    Ball(int x, int y){
        this->x = x;
        this->y = y;
    }
};

class BallGroup {
public:
    Ball* red;
    Ball* blue;
    int count;
    DIRECTION direction;
    BallGroup(){
        this->count =0;
        this->direction = NONE;
    }
    BallGroup(DIRECTION direction){
        this->count =0;
        this->direction = direction;
    }
    BallGroup(Ball* red, Ball* blue, DIRECTION direction,int count){
        this->count =count;
        this->red = red;
        this->blue = blue;
        this->direction = direction;
    }
    ~BallGroup(){
        delete red;
        delete blue;
    }
};

int n,m;
vector<vector<int> > map(10,vector<int>(10));

bool isRange(int x, int y){
    return x>0 && x<m && y>0 && y<n;
}
bool isMatch(int xa, int ya, int xb, int yb){
    return xa==xb && ya == yb;
}

BallGroup* nextBG(BallGroup* bg,Ball* goal, DIRECTION direction,int ax, int ay){
    
    //이전 방향과 같으면 nullptr
    if(bg->direction == direction)return nullptr;
    if(bg->count >= 10)return nullptr;
    int rx = bg->red->x, ry = bg->red->y;
    int bx = bg->blue->x, by = bg->blue->y;
    int next_count = (bg->count)+1;
    
    //red 길 끝까지 또는 출구까지
    while(isRange(rx+ax,ry+ay)&& map[ry+ay][rx+ax]==1 ){
        rx+=ax;
        ry+=ay;
        if(isMatch(rx, ry, goal->x, goal->y))break;
    }
    //blue 길 끝까지 또는 출구까지
    while(isRange(bx+ax,by+ay)&& map[by+ay][bx+ax]==1 ){
        bx+=ax;
        by+=ay;
        if(isMatch(bx, by, goal->x, goal->y))break;
    }
    
    if(isMatch(rx, ry, bx, by)){
        if(isMatch(rx, ry, goal->x, goal->y)){
            //둘다 빠졌을 때
            return nullptr;
        }else{
            if(direction ==TOP){
                if(bg->red->y > bg->blue->y){
                    ry++;
                }else{
                    by++;
                }
            }else if(direction==BOTTOM){
                if(bg->red->y > bg->blue->y){
                    by--;
                }else{
                    ry--;
                }

            }else if(direction==LEFT){
                if(bg->red->x > bg->blue->x){
                    rx++;
                }else{
                    bx++;
                }

            }else if(direction==RIGHT){
                if(bg->red->x > bg->blue->x){
                    bx--;
                }else{
                    rx--;
                }
            }
            if(isMatch(rx, ry, bg->red->x, bg->red->y)&& isMatch(bx, by, bg->blue->x, bg->blue->y)){
                return nullptr;
            }else{
                return new BallGroup(new Ball(rx,ry),new Ball(bx,by),direction,next_count);
            }
        }
    }else{
        if(isMatch(rx, ry, bg->red->x, bg->red->y)&& isMatch(bx, by, bg->blue->x, bg->blue->y)){
            return nullptr;
        }else{
            return new BallGroup(new Ball(rx,ry), new Ball(bx,by),direction,next_count);
        }
    }
}

int getCount(BallGroup* bg, Ball* goal){
    int count = -1;
    queue<BallGroup*> q;
    q.push(bg);
    
    
    while(!q.empty()){
        BallGroup* cur = q.front();
        q.pop();
        
        //cout <<"c : "<<cur.count<<" d : "<<cur.direction<<" ("<< cur.red.x <<", "<<cur.red.y <<") ("<<cur.blue.x<<", "<<cur.blue.y<<")"<<endl;
        
        if(isMatch(cur->red->x, cur->red->y, goal->x, goal->y)){
            count = cur->count;
            break;
        }
        
        
        BallGroup* top = nextBG(cur,goal,TOP,0,-1);
        if(top!=nullptr)q.push(top);

        BallGroup* bottom = nextBG(cur,goal,BOTTOM,0,1);
        if(bottom!=nullptr)q.push(bottom);

        BallGroup* left = nextBG(cur,goal,LEFT,-1,0);
        if(left!=nullptr)q.push(left);

        BallGroup* right = nextBG(cur,goal,RIGHT,1,0);
        if(right!=nullptr)q.push(right);
        
        delete cur;
    }
    
    return count;
}

int main(){
    cin >>n>>m;
    
    int rx=0,ry=0,bx=0,by=0,gx=0,gy=0;
    for(int i =0; i<n;i++){
        for(int j =0; j<m;j++){
            char c;
            cin >>c;
            if(c=='.'){
                map[i][j] = 1;
            }else if(c=='R'){
                map[i][j] = 1;
                rx = j;
                ry = i;
            }else if(c=='B'){
                map[i][j] = 1;
                bx = j;
                by = i;
            }else if(c=='O'){
                map[i][j] = 1;
                gx = j;
                gy = i;
            }else{
                map[i][j] = 0;
            }
        }
    }
    Ball* goal = new Ball(gx,gy);
    BallGroup* bg = new BallGroup(new Ball(rx,ry),new Ball(bx,by),NONE,0);

    cout << getCount(bg,goal);
    
    return 0;
}

djm03178 5년 전 0

반례들입니다.

5 4
####
#.##
#O##
#BR#
####
output: 3
correct answer: -1

5 5
#####
#R###
#.OB#
#.#.#
#####
output: 5
correct answer: -1

5 5
#####
#B..#
#..R#
#O#.#
#####
output: 9
correct answer: -1

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

문제

문제

출처

ICPC

구슬 탈출 틀린 예시를 모르겠네요

homs44 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말