글 읽기 - 빙산 코드..?

kim08 5년 전 0

이거 왜 매모리 초과죠?

이상합니다....

#include <stdio.h>
#define M 10000
int cnt;
int row,col;
struct vecter{
    int x;
    int y;
};
vecter q[M+5];
int g[M+5][M+5];
int g2[M+5][M+5];
int vt[M+5][M+5];
void in(){
    scanf("%d %d",&row,&col);
    int i,j;
    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
            scanf("%d",&g[i][j]);
        }
    }
}
int bfs2(int x,int y){
    int i,j;
    int f=0,r=0;
    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
            if(g[i][j]==0){
                vt[i][j]=1;
            }else{
                vt[i][j]=0;
                cnt--;
                if(g[i][j-1]!=0||g[i][j+1]!=0||g[i-1][j]!=0||g[i+1][j]!=0) cnt++;
            }
        }
    }
    vecter t;
    do{
        t=q[f++];
        if(t.x-1>=0&&vt[t.x-1][t.y]==0){
            q[r++]={t.x-1,t.y};
            vt[t.x-1][t.y]=1;
        }
        if(t.x+1<row&&vt[t.x+1][t.y]==0){
            q[r++]={t.x+1,t.y};
            vt[t.x+1][t.y]=1;
        }
        if(t.y-1>=0&&vt[t.x][t.y-1]==0){
            q[r++]={t.x,t.y-1};
            vt[t.x][t.y-1]=1;
        }
        if(t.y+1<col&&vt[t.x][t.y+1]==0){
            q[r++]={t.x,t.y+1};
            vt[t.x][t.y+1]=1;
        }
    }while (f!=r);
    return r;
}
int check(){
    int i,j;
    int t=1;
    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
            cnt=0;
            if(g2[i][j]>0){
                t=bfs2(i,j);
                if(cnt<0) return 1;
                if(t==cnt) return 0;
            }
        }
    }
    return -1;
}
void bfs(){
    int i,j;
    int f=0,r=0;
    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
            g2[i][j]=g[i][j];
            if(g[i][j]==0){
                vt[i][j]=1;
            }else{
                q[r++]={i,j};
                vt[i][j]=0;
            }
        }
    }
    vecter t;
    int tt;
    do{
        t=q[f++];
        vt[t.x][t.y]=1;
        tt=0;
        if(t.x-1>=0&&g[t.x-1][t.y]==0) tt++;
        if(t.x+1<row&&g[t.x+1][t.y]==0) tt++;
        if(t.y-1>=0&&g[t.x][t.y-1]==0) tt++;
        if(t.y+1<col&&g[t.x][t.y+1]==0) tt++;
        g2[t.x][t.y]-=tt;
        if(g2[t.x][t.y]<0) g2[t.x][t.y]=0;
    }while(f!=r);
    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
            g[i][j]=g2[i][j];
        }
    }
}
int main(){
    in();
    int y=0;
    int group=2222;
    while(1){
        group=check();
        if(group==0){
            y=0;
            break;
        }if(group<0){
            break;
        }
        bfs();
        y++;
    }
    printf("%d\n",y);
    return 0;
}

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

문제

문제

출처

ICPC

빙산 코드..?

kim08 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말