글 읽기 - 틀린 이유를 모르겠습니다....

superm 5년 전 0

테스트케이스 5개 확인을 했는데 모두 답이 잘나옵니다
하지만 결과로는 틀렸다고하는데 어디가 틀렸는지 잘모르겠네요 흑흑
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;

typedef pair<int, int> node;

int n,m,h;
int turn,height;
char map[MAX][MAX];
int visited[MAX][MAX];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

vector<node> cluster;

// 맵의 모양을 출력
void printMap(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << map[i][j];
        }
        cout << "\n";
    }
}

// 막대기를 던져 미네랄을 파괴함
bool throwStick(){
    int i = n - height;
    // 왼쪽 → 오른쪽
    if(turn == 1){
        for(int j=0; j<m; j++){
            if(map[i][j] == 'x'){
                map[i][j] = '.';
                return true;
            }
        }
    }
    // 오른쪽 → 왼쪽
    else if(turn == -1){
        for(int j=m-1; j>=0; j--){
            if(map[i][j] == 'x'){
                map[i][j] = '.';
                return true;
            }
        }
    }
    return false;
}

// 클러스터의 노드 중, 바닥에 붙어있는 노드가 있는지 검사
bool bfs(int r,int c){
    queue<node> q;
    q.push(node(r,c));
    visited[r][c] = 1;
    cluster.push_back(node(r,c));
    bool flag = false;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x == n-1){
            flag = true;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
            
            if(visited[nx][ny]==0 && map[nx][ny]=='x'){
                q.push(node(nx,ny));
                visited[nx][ny] = 1;
                cluster.push_back(node(nx,ny));
            }
        }
    }
    return flag;
}

// 클러스트를 중력에 의해 내림
void cluster_down(){
    while(true){
        bool loop = true;
        
        // 해당 클러스터를 지움
        for(int i=0; i<cluster.size(); i++){
            int x = cluster[i].first;
            int y = cluster[i].second;
            map[x][y] = '.';
            visited[x][y] = 0;
        }
        
        // 클러스터 검사
        for(int i=0; i<cluster.size(); i++){
            int x = cluster[i].first + 1;
            int y = cluster[i].second;
            
            if(map[x][y]=='x' || x==n){
                loop = false;
                break;
            }
        }
        
        // 한칸 내리기
        if(loop){
            for(int i=0; i<cluster.size(); i++){
                int x = cluster[i].first + 1;
                int y = cluster[i].second;
                
                cluster[i].first += 1;
                map[x][y] = 'x';
                visited[x][y] = 1;
            }
        }
        // 다시 원상복귀
        else{
            for(int i=0; i<cluster.size(); i++){
                int x = cluster[i].first;
                int y = cluster[i].second;
                
                map[x][y] = 'x';
                visited[x][y] = 1;
            }
            cluster.clear();
            return;
        }
    }
}

// 맵의 전체를 돌며 클러스트를 구함
void go(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(visited[i][j]==0 && map[i][j]=='x'){
                // 만약 클러스트의 노드 중에 바닥에 붙어있는 노드가 없다면
                if(!bfs(i,j)){
                    cluster_down();
                    return;
                }
                cluster.clear();
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 맵 입력
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    
    turn = 1;
    
    cin >> h;
    for(int i=0; i<h; i++){
        cin >> height;
        // 막대기를 던져 미네랄 파괴
        // 파괴된게 없으면 continue
        if(!throwStick()) continue;
        
        // 파괴 후, 맵의 변화를 파악
        memset(visited, 0, sizeof(visited));
        go();
        
        // 턴을 변경함
        turn *= -1;
    }
    printMap();
    
    return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

틀린 이유를 모르겠습니다....

superm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
