글 읽기 - 계속틀리는데 혹시 무엇이 잘못일까요?

kdk 2년 전 0

입력을 받고 detercluster함수에서 붕뜬 클러스터가 있는지 찾습니다.

이때 붕뜬 클러스터가 없으면 넘어가고 있다면 check배열에 3으로 저장하고 안뜬 클러스터는 2로 저장합니다.

이후에 얼만큼내려가야하는지 구해 minps에 저장하고 check 배열에서 3인 녀석들을 아래부터 내려서(코드상으론 숫자큰거부터) 내림작업을 완료합니다.

인데... 9%에서 틀리네요.. 혹시 무엇이 잘못됬을까요? 기존 질문들에서 이야기한 반례들은 다 통과되는거같은데 혹시 로직이 잘못되었는지 알려주시면 감사하겠습니다...

#include <bits/stdc++.h>
//2933
using namespace std;

int r,c;
char psmap[100][100];
int stick[102];
int dir[4][2] = { 0,1,0,-1,1,0,-1,0 };
short check[100][100];


bool detercluster(void){

	for (int b = 0; b < c; b++){
		for (int a = 0; a < r; a++){
			check[a][b] =  0;
		}
	}
	queue<pair<int, int>> q;
	bool flag = 0;

		for (int i = r - 1; i > -1; i--){
			for (int j = 0; j < c; j++){
				if (psmap[i][j] == 'x'&&check[i][j] == 0){
					if (i != r - 1){
						flag = 1;
						check[i][j] = 3;
					}
					else{
						check[i][j] = 2;
					}
					q.push({ i,j });
					
					while (!q.empty()){
						
						int x, y;
						for (int z = 0; z < 4; z++){
							 x = q.front().first + dir[z][0];
							 y = q.front().second + dir[z][1];
							if (x >= r || x < 0 || y >= c || y < 0)
								continue;
							if (psmap[x][y] == 'x'&&check[x][y]==0){
								if (i != r - 1){
									check[x][y] = 3;
								}
								else{
									check[x][y] = 2;
								}
								q.push({ x,y });
							}

						}
						q.pop();
					}

				}
			}
		}
		
		return flag;
}

int main(void)
{
	//freopen("input.txt", "r", stdin);
	
	scanf("%d %d", &r, &c);
	
	for (int i = 0; i < r; i++)
	scanf("%s", psmap[i]);
	
	
	scanf("%d", &stick[0]);
	for (int i = 1; i <= stick[0]; i++)
	scanf(" %d", &stick[i]);
	
	
	for (int i = 1; i <= stick[0]; i++){
	
		if (i % 2 == 1){
			for (int j = 0; j < c; j++){
				if (psmap[r-stick[i]][j] == 'x'){
					psmap[r-stick[i]][j] = '.';
					break;
				}
			}
		}
		else{
			for (int j = c - 1; j > -1; j--){
				if (psmap[r-stick[i]][j] == 'x'){
					psmap[r-stick[i]][j] = '.';
					break;
				}
			}
		}
		
// 클러스터 결정 및 떨구기 
		if (detercluster()){
			int minps = r;
			for (int b = 0; b < c; b++){
				int temp = r;
				for (int a = r-1; a > -1; a--){
					if (check[a][b] == 2)
					temp = a;

					if (check[a][b] == 3)
                    minps = min(minps, temp-1 - a);
					
				}
			}
			
			for (int b = 0; b < c; b++){
				for (int a = r-1; a > -1; a--){
					if (check[a][b] == 3){
						psmap[a][b] = '.';
						psmap[a + minps][b] = 'x';
					}
				}
			}
		
		}
		
	}

	for (int i = 0; i < r; i++)
	printf("%s\n", psmap[i]);
		
	



	return 0;

}

kdk 2년 전 0

배열 정의에서 범위 수정하여 해결하였습니다.

#include <bits/stdc++.h>
//2933
using namespace std;

int r,c;
char psmap[101][101];
int stick[102];
int dir[4][2] = { 0,1,0,-1,1,0,-1,0 };
short check[101][101];

bool detercluster(void){

    for (int b = 0; b < c; b++){
        for (int a = 0; a < r; a++){
            check[a][b] =  0;
        }
    }
    queue<pair<int, int>> q;
    bool flag = 0;

        for (int i = r - 1; i > -1; i--){
            for (int j = 0; j < c; j++){
                if (psmap[i][j] == 'x'&&check[i][j] == 0){
                    if (i != r - 1){
                        flag = 1;
                        check[i][j] = 3;
                    }
                    else{
                        check[i][j] = 2;
                    }
                    q.push({ i,j });
                    
                    while (!q.empty()){
                        
                        int x, y;
                        for (int z = 0; z < 4; z++){
                             x = q.front().first + dir[z][0];
                             y = q.front().second + dir[z][1];
                            if (x >= r || x < 0 || y >= c || y < 0)
                                continue;
                            if (psmap[x][y] == 'x'&&check[x][y]==0){
                                if (i != r - 1){
                                    check[x][y] = 3;
                                }
                                else{
                                    check[x][y] = 2;
                                }
                                q.push({ x,y });
                            }
                        }
                        q.pop();
                    }

                }
            }
        }
        
        return flag;
}

int main(void)
{
   // freopen("input.txt", "r", stdin);
    
    scanf("%d %d", &r, &c);
    
    for (int i = 0; i < r; i++)
    scanf("%s", psmap[i]);
    
    scanf("%d", &stick[0]);
    for (int i = 1; i <= stick[0]; i++)
    scanf(" %d", &stick[i]);
    
    for (int i = 1; i <= stick[0]; i++){
    
        if (i % 2 == 1){
            for (int j = 0; j < c; j++){
                if (psmap[r-stick[i]][j] == 'x'){
                    psmap[r-stick[i]][j] = '.';
                    break;
                }
            }
        }
        else{
            for (int j = c - 1; j > -1; j--){
                if (psmap[r-stick[i]][j] == 'x'){
                    psmap[r-stick[i]][j] = '.';
                    break;
                }
            }
        }
        
// 클러스터 결정 및 떨구기
        if (detercluster()){
            int minps = r;
            for (int b = 0; b < c; b++){
                int temp = r;
                for (int a = r-1; a > -1; a--){
                    if (check[a][b] == 2)
                    temp = a;
                    if (check[a][b] == 3)
                    minps = min(minps, temp-1 - a);
                }
            }
            for (int b = 0; b < c; b++){
                for (int a = r-1; a > -1; a--){
                    if (check[a][b] == 3){
                        psmap[a][b] = '.';
                        psmap[a + minps][b] = 'x';
                    }
                }
            }
        }
        
    }

    for (int i = 0; i < r; i++)
    printf("%s\n", psmap[i]);
        
    return 0;

}

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

문제

문제

출처

ICPC

계속틀리는데 혹시 무엇이 잘못일까요?

kdk 2년 전 0

kdk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말