글 읽기 - 반례좀 찾아주세요

didwlvv 7년 전 0

체크 배열을 3개 만들어서 3개다 체크가 되어있지 않으면 가는식으로 짰는데 머가 틀린지 모르겠습니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
struct Data{
    int y1,x1;
    int y2,x2;
    int y3,x3;
    int cnt;
};
Data temp;
int chk[105][105];
int chk1[105][105];
int chk2[105][105];

char map[105][105];
int n;

int dy[4] ={-1,1,0,0};
int dx[4] ={0,0,1,-1};
bool Range(int x, int y){
    if(x < 0 || y<0  || x>n-1 || y>n-1)
        return false;
    return true;
}


void init();    void solve();

int main(){
    init();
    solve();
    
    return 0;
}

void init(){
    int idx=0;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf(" %c", &map[i][j]);
            if(map[i][j] =='B'){
                if(idx==0){
                    idx++;
                    temp.y1=i;
                    temp.x1=j;
                }
                else if( idx==1){
                    temp.y2 = i;
                    temp.x2=j;
                    idx++;
                }
                else if(idx==2){
                    temp.y3=i;
                    temp.x3=j;
                    idx++;
                }
            }
        }
    }
    
    return;
}

void solve(){
    queue<Data>q;
    chk[temp.y1][temp.x1]=1;
    chk1[temp.y2][temp.x2]=1;
    chk2[temp.y3][temp.x3]=1;
    q.push(temp);
    
    while(!q.empty()){
        Data now =q.front();q.pop();
        // cout << now.y1<<now.x1 <<" "<<now.y2<<now.x2<<" "<<now.y3<<now.x3<<endl;
        if(map[now.y1][now.x1]=='E' && map[now.y2][now.x2]=='E' && map[now.y3][now.x3]=='E'){
            cout << now.cnt <<endl;
            return;
        }
        
        for(int i=0; i<4; i++){
            Data next;
            next.y1 = now.y1 +dy[i];
            next.y2 = now.y2 +dy[i];
            next.y3 = now.y3 +dy[i];
            next.x1 = now.x1 +dx[i];
            next.x2 = now.x2 +dx[i];
            next.x3 = now.x3 +dx[i];
            next.cnt = now.cnt +1;
            if(Range(next.x1, next.y1) && Range(next.x2, next.y2) && Range(next.x3, next.y3)){
                if(map[next.y1][next.x1] !='1' && map[next.y2][next.x2] !='1' && map[next.y3][next.x3] !='1'){
                    if(chk[next.y1][next.x1]==0 || chk1[next.y2][next.x2]==0 || chk2[next.y3][next.x3]==0){
                        chk[next.y1][next.x1]=1;
                        chk1[next.y2][next.x2]=1;
                        chk2[next.y3][next.x3]=1;
                        
                        q.push(next);
                    }
                }
            }
        }
        
        if(now.y1 == now.y2 && now.y2 == now.y3){
            if(Range(now.x1,now.y1-1) && Range(now.x1,now.y1+1) && Range(now.x2,now.y2-1)
               && Range(now.x2,now.y2+1) && Range(now.x3,now.y3-1) && Range(now.x3,now.y3+1)){
                if(map[now.y1-1][now.x1] !='1' && map[now.y1+1][now.x1] !='1'){
                    if(map[now.y2-1][now.x2] !='1' && map[now.y2+1][now.x2] !='1'){
                        if(map[now.y3-1][now.x3] !='1' && map[now.y3+1][now.x3] !='1'){
                            Data next;
                            next.y1 = now.y1 -1;
                            next.x1 = now.x1 +1;
                            next.y2=now.y2;
                            next.x2=now.x2;
                            next.y3 = now.y3 +1;
                            next.x3 = now.x3 -1;
                            next.cnt = now.cnt +1;
                            if(chk[next.y1][next.x1]==0 || chk1[next.y2][next.x2]==0 || chk2[next.y3][next.x3]==0){
                                chk[next.y1][next.x1]=1;
                                chk1[next.y2][next.x2]=1;
                                chk2[next.y3][next.x3]=1;

                                q.push(next);
                            }
                        }
                        
                    }
                }
            }
        }
        else{
            if(Range(now.x1-1,now.y1) && Range(now.x1+1,now.y1) && Range(now.x2-1,now.y2)
               && Range(now.x2+1,now.y2) && Range(now.x3-1,now.y3) && Range(now.x3+1,now.y3)){
                if(map[now.y1][now.x1-1] !='1' && map[now.y1][now.x1 +1] !='1'){
                    if(map[now.y2][now.x2-1] !='1' && map[now.y2][now.x2 +1] !='1'){
                        if(map[now.y3][now.x3-1] !='1' && map[now.y3][now.x3 +1] !='1'){
                            Data next;
                            next.y1 = now.y1 +1;
                            next.x1 = now.x1 -1;
                            next.y2=now.y2;
                            next.x2= now.x2;
                            next.y3 = now.y3 -1;
                            next.x3 = now.x3 +1;
                            next.cnt = now.cnt+1;
                            if(chk[next.y1][next.x1]==0 || chk1[next.y2][next.x2]==0 || chk2[next.y3][next.x3]==0){
                                chk[next.y1][next.x1]=1;
                                chk1[next.y2][next.x2]=1;
                                chk2[next.y3][next.x3]=1;

                                q.push(next);
                            }
                        }
                        
                    }
                    
                }
            }
        }
    }
    cout<<"0"<<endl;
    return;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례좀 찾아주세요

didwlvv 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
