글 읽기 - 반례 찾아주시면 감사하겠습니다.

susu27 3년 전 0

테스트케이스는 다 통과하는데 틀렸습니다가 뜨네요 ㅠㅠ
#include <bits/stdc++.h>

using namespace std;

int red[4][4]={0, };
int blue[4][6]={0, };
int green[6][4]={0, };
int result=0;
int N;

void print(){
    printf("green\n");
        for(int i=0; i<6; i++){
            for(int j=0; j<4; j++){
                printf("%d ", green[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        
        printf("blue\n");
        for(int i=0; i<4; i++){
            for(int j=0; j<6; j++){
                printf("%d ", blue[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        
        printf("----------------------------------------\n");
}

int find(){
    for(int i=0; i<6; i++){
        int cnt=0;
        for(int j=0; j<4; j++){
            if(green[i][j]) cnt++;
        }
        if(cnt==4) return 1;
    }
    
    for(int i=0; i<6; i++){
        int cnt=0;
        for(int j=0; j<4; j++){
            if(blue[j][i]) cnt++;
        }
        if(cnt==4) return 0;
    }
    
    return 2;
}

bool special(){
    for(int i=0; i<2; i++){
        for(int j=0; j<4; j++){
            if(green[i][j]) return true;
            if(blue[j][i]) return true;
        }
    }
    
    return false;
}

void remove_b(){
    for(int i=0; i<6; i++){
        int cnt=0;
        for(int j=0; j<4; j++){
            if(green[i][j]) cnt++;
        }
        if(cnt==4){
            for(int j=0; j<4; j++) green[i][j] = 0;
            for(int x=i; x>0; x--){
                for(int y = 0; y<4; y++){
                    green[x][y] = green[x-1][y];
                }
            }
            return;
        } 
    }
    
    for(int i=0; i<6; i++){
        int cnt=0;
        for(int j=0; j<4; j++){
            if(blue[j][i]) cnt++;
        }
        if(cnt==4){
            for(int j=0; j<4; j++) blue[j][i] = 0;
            for(int y=i; y>0; y--){
                for(int x=0; x<4; x++){
                    blue[x][y] = blue[x][y-1];
                }
            }
            return;
        } 
    }
}






int b_block(int x, int y, bool first){
    if(y==5) return 5;
    int start;
    if(first) start = 0;
    else start = y;
    for(int i=start; i<6; i++){
        if(blue[x][i]>0){
            return i-1;
        }
    }
    
    return 5;
}

int g_block(int x, int y, bool first){
    if(x==5) return 5;
    int start;
    if(first) start = 0;
    else start = x;
    for(int i=start; i<6; i++){
        if(green[i][y]>0){
            return i-1;
        }
    }
    
    return 5;
}

void move(int color, int x, int y){
    queue<pair<int,int>> q;
    q.push({x,y});
    vector <pair<int,int>> v;
    int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
    bool check[6][6]={0, };    
    if(color == 0){  //blue
        int index = blue[x][y];
        blue[x][y] = 0;
        while(!q.empty()){
            pair <int,int> cur = q.front();
            q.pop();
            v.push_back(cur);
            for(int i=0; i<4; i++){
                int nx = cur.first + dx[i];
                int ny = cur.second + dy[i];
                
                if(nx>=4 || nx <0 || ny>=6 || ny<0) continue;
                if(check[nx][ny]) continue;
                check[nx][ny] = true;
                if(blue[nx][ny]==index){
                    q.push({nx,ny});
                    blue[nx][ny]=0;
                }
            }
        }
        //printf("%d %d\n", index, v.size());
        if(v.size()==1){
            int next = b_block(v[0].first,v[0].second, false);
            blue[v[0].first][next] = index;
        }
        else if(v.size()==2){
            if(v[0].first==v[1].first){
                int next = b_block(v[0].first,max(v[0].second, v[1].second), false);
                blue[v[0].first][next] = index;
                blue[v[1].first][next-1] = index;
            }
            else{
                int one = b_block(v[0].first,v[0].second, false);
                int two = b_block(v[1].first,v[1].second, false);
                int next = min(one,two);
                //printf("%d %d\n", index, next);
                blue[v[0].first][next] = index;
                blue[v[1].first][next] = index;
            }
        }
    }
    else{ //green
        int index = green[x][y];
        green[x][y] = 0;
        while(!q.empty()){
            pair <int,int> cur = q.front();
            q.pop();
            v.push_back(cur);
            for(int i=0; i<4; i++){
                int nx = cur.first + dx[i];
                int ny = cur.second + dy[i];
                
                if(ny>=4 || ny <0 || nx>=6 || nx<0) continue;
                if(check[nx][ny]) continue;
                check[nx][ny] = true;
                if(green[nx][ny]==index){
                    q.push({nx,ny});
                    green[nx][ny]=0;
                }
            }
        }
           
        if(v.size()==1){
            int next = g_block(v[0].first,v[0].second, false);
            green[next][v[0].second] = index;
        }
        else if(v.size()==2){
            if(v[0].first==v[1].first){
                int one = g_block(v[0].first,v[0].second, false);
                int two = g_block(v[1].first,v[1].second, false);
                int next = min(one, two);
                green[next][v[0].second] = index;
                green[next][v[1].second] = index;
            }
            else{
                int next = g_block(max(v[0].first, v[1].first),y, false);
                green[next][v[0].second] = index;
                green[next-1][v[0].second] = index;
            }
        }
    }
}

void move_b(int color, int index){
    bool check[N+1]={0, };
    if(color == 0){ //blue
        //for(int i=0; i<4; i++) blue[i][index] = 0;
        for(int i=index-1; i>0; i--){
            for(int j=0; j<4; j++){
                if(blue[j][i]>0 && !check[blue[j][i]]){
                    move(color, j, i);
                    check[blue[j][i]] = true;
                }
            }
        }
    }
    else{ //green
        //for(int i=0; i<4; i++) green[index][i] = 0;
        for(int i=index-1; i>0; i--){
            for(int j=0; j<4; j++){
                if(green[i][j]>0 && !check[green[i][j]]){
                    move(color, i, j);
                    check[green[i][j]] = true;
                }
            }
        }
    }
}

void special_remove(){
    int g_cnt=0, b_cnt=0;
    for(int i=0; i<2; i++){
        for(int j=0; j<4; j++){
            if(green[i][j]){
                g_cnt++;
                break;
            }
            
        }
        for(int j=0; j<4; j++){
            
            if(blue[j][i]){
                b_cnt++;
                break;
            }
        }
    }
    
    
    for(int i=0; i<g_cnt; i++){
        for(int j=0; j<4; j++) green[5-i][j] = 0;
    } 
    move_b(1,5);
    
    
    for(int i=0; i<b_cnt; i++){
        for(int j=0; j<4; j++) blue[j][5-i] = 0;
    } 
    move_b(0,5);
}

void getResult(int t, int x, int y, int index){
    if(t==1){
        int next = g_block(x,y,true);
        green[next][y] = index;
        next = b_block(x,y,true);
        blue[x][next] = index;
    }
    else if(t==2){
        int one = g_block(x,y,true);
        int two = g_block(x,y+1,true);
        int next = min(one, two);
        green[next][y] = index;
        green[next][y+1] = index;
        
        next = b_block(x,y+1,true);
        blue[x][next] = index;
        blue[x][next-1] = index;
    }
    else if(t==3){
        int next = g_block(x+1,y, true);
        green[next][y] = index;
        green[next-1][y] = index;
        
        int one = b_block(x,y,true);
        int two = b_block(x+1,y,true);
        next = min(one,two);
        blue[x][next] = index;
        blue[x+1][next] = index;
    }
    
    //print();
    
    int color = find();
    while(color!=2){
        remove_b();
        color = find();
        result++;
        //printf("remove\n");
        //print();
    } 

    if(special()){
        special_remove();
        //printf("special\n");
        //print();
    }
}

int getCnt(){
    int cnt = 0;
    
    for(int i=0; i<6; i++){
        for(int j=0; j<4; j++){
            if(green[i][j]) cnt++;
        }
    }

    for(int i=0; i<4; i++){
        for(int j=0; j<6; j++){
            if(blue[i][j]) cnt++;
        }
    }
    
    return cnt;
}

int main() {
    
    scanf("%d", &N);
    
    for(int i=0; i<N; i++){
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y);
        getResult(t,x,y, i+1);
        //print();
    }
    printf("%d\n%d\n", result, getCnt());
    return 0;
}
kimmoon4 3년 전 1

혹시 맞은것을 삭제하실때 연한 파랑, 초록 영역의 것들까지 다 이동시켜주는 작업을 하셨나요?
statco19 2년 전 0

@kimmoon4 덕분에 시작하자마자 틀렸습니다 나오는 부분을 해결하였습니다. 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례 찾아주시면 감사하겠습니다.

susu27 3년 전 0

kimmoon4 3년 전 1

statco19 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
