글 읽기 - 테케와 반례는 성공했는데 어디서 틀린지 모르겠습니다

hannnn 3년 전 0

테스트케이스와 아래 반례는 해결했습니다.

https://www.acmicpc.net/board/view/50089

그런데 제출하면 틀리다고 나옵니다.

틀린부분 알려주신다면 정말 감사하겠습니다.

#include <iostream>
#include <deque>
#include <queue>
using namespace std;
int n,m,t;
int a,b,c;
deque<int> C[50];
queue<pair<int,int>> q;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int cnt=0;
bool nothing=false;

int sum(){
    int ans=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(C[i][j]!=0){
                ans+=C[i][j];
                cnt++;
            }
        }
    }
    return ans;
}

void BFS(int x, int y, int d){    
    while(!q.empty()) q.pop();
    q.push(make_pair(x,y));
    while(!q.empty()){
        int _x = q.front().first;
        int _y = q.front().second;
        if(_y==0 && C[_x][m-1]==d){ // (i,0)과 (i,m-1) 해결
            C[_x][m-1]=0;
            nothing = true;
        }
        else if(_y==m-1 && C[_x][0]==d){ // (i,0)과 (i,m-1) 해결
            C[_x][0]=0;
            nothing = true;
        }
        q.pop();
        for(int idx=0; idx<4; idx++){
            int nx = _x + dx[idx];
            int ny = _y + dy[idx];
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(C[nx][ny]!=d) continue; // 범위 밖 또는 d가 아닌 경우
            if(C[nx][ny]==d){ 
                C[_x][_y]=0; 
                C[nx][ny]=0;
                nothing = true;
                q.push(make_pair(nx,ny));
            }
        }
    }
}
void remove(){
    nothing=false;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(C[i][j]!=0) BFS(i,j,C[i][j]);
        }
    }
    if(!nothing){ // 변경된 것이 없는 경우
        cnt=0;
        double s = (double)sum();
        if(cnt==0) return;
        double mean = s/cnt;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(C[i][j]!=0){
                    if(C[i][j]>mean) C[i][j]-=1;
                    else if(C[i][j]<mean) C[i][j]+=1;
                }
            }
        }
    }
}
void rotate(int x, int d, int k){
    for(int i=0; i<n; i++){
        if((i+1)%x==0){ // 1) x의 배수
            int cnt=k;
            if(d==0){ // 2-1) clockwise
                while(cnt--){
                    int tmp = C[i].back();
                    C[i].pop_back();
                    C[i].push_front(tmp);
                }
            }
            else{ // 2-2) counter clockwise
                while(cnt--){
                    int tmp = C[i].front();
                    C[i].pop_front();
                    C[i].push_back(tmp);
                }
            }
        }
    }
    remove();
}
int main(){
    cin >> n >> m >> t;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int num;
            cin >> num;
            C[i].push_back(num);
        }
    }
    for(int i=0; i<t; i++){
        cin >> a >> b >> c;
        rotate(a,b,c);
    }
    cout << sum();
    return 0;
}

hannnn 3년 전 0

해결했습니다.

추가된 부분은 '추가했습니다☆★☆★☆★'로 표시해두었습니다.

#include <iostream>
#include <deque>
#include <queue>
using namespace std;
int n,m,t;
int a,b,c;
deque<int> C[50];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int cnt=0;
bool flag=false;

int sum(){
    int int_s=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(C[i][j]!=0){
                int_s+=C[i][j];
                cnt++;
            }
        }
    }
    return int_s;
}

void BFS(int x, int y, int d){    
    queue<pair<int,int>> q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        int _x = q.front().first;
        int _y = q.front().second;
        if(_y==0 && C[_x][m-1]==d){ // (i,m-1) 해결 후 queue 삽입
            C[_x][_y]=0; // 추가했습니다☆★☆★☆★☆★
            C[_x][m-1]=0;
            q.push(make_pair(_x,m-1)); // 추가했습니다☆★☆★☆★
            flag = true;
        }
        if(_y==m-1 && C[_x][0]==d){ // (i,0) 해결 후 queue 삽입
            C[_x][_y]=0; // 추가했습니다☆★☆★☆★
            C[_x][0]=0;
            q.push(make_pair(_x,0)); // 추가했습니다☆★☆★☆★
            flag = true;
        }
        q.pop();
        for(int idx=0; idx<4; idx++){
            int nx = _x + dx[idx];
            int ny = _y + dy[idx];
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(C[nx][ny]!=d) continue; // 범위 밖 또는 d가 아닌 경우
            if(C[nx][ny]==d){ 
                C[_x][_y]=0; 
                C[nx][ny]=0;
                flag = true;
                q.push(make_pair(nx,ny));
            }
        }
    }
}
void remove(){
    flag=false;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(C[i][j]!=0) BFS(i,j,C[i][j]);
        }
    }
    if(!flag){ // 변경된 것이 없는 경우
        cnt=0;
        double ds = (double)sum();
        if(cnt==0) return;
        double mean = ds/cnt;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(C[i][j]!=0){
                    if(C[i][j]>mean) C[i][j]-=1;
                    else if(C[i][j]<mean) C[i][j]+=1;
                }
            }
        }
    }
}
void rotate(int x, int d, int k){
    for(int i=0; i<n; i++){
        if((i+1)%x==0){ // 1) x의 배수
            int cnt=k;
            if(d==0){ // 2-1) clockwise
                while(cnt--){
                    int tmp = C[i].back();
                    C[i].pop_back();
                    C[i].push_front(tmp);
                }
            }
            else{ // 2-2) counter clockwise
                while(cnt--){
                    int tmp = C[i].front();
                    C[i].pop_front();
                    C[i].push_back(tmp);
                }
            }
        }
    }
    remove();
}
int main(){
    cin >> n >> m >> t;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int num;
            cin >> num;
            C[i].push_back(num);
        }
    }
    for(int i=0; i<t; i++){
        cin >> a >> b >> c;
        rotate(a,b,c);
    }
    cout << sum();
    return 0;
}

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

문제

문제

출처

ICPC

테케와 반례는 성공했는데 어디서 틀린지 모르겠습니다

hannnn 3년 전 0

hannnn 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말