글 읽기 - 메모리 초과...

iron1209 4년 전 0

메모리 초과는 잘 모르겠습니다.

dfs가 문제일까요?

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
char M[1003][1003], chk[1003][1003];//-1 방문 안함 양수면 방문함
int z_cnt[500003], cnt, idx;
int x_l[4]={0,0,1,-1};
int y_l[4]={1,-1,0,0};
int n,m;

int dfs(int y, int x){
    int ret=1;
    chk[y][x]=idx;
    for(int i=0;i<4;i++){
        int ny=y+y_l[i], nx=x+x_l[i];
        if(ny>=0 && ny<n && nx>=0 && nx<m){
            if(chk[ny][nx]==-1) ret+=dfs(ny,nx);
        }
    }
    return ret;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>M[i][j];
            if(M[i][j]=='0'){
                chk[i][j]=-1; M[i][j]=0;
            }
            else{
                chk[i][j]=0; M[i][j]=1;
            }
        }
    }
    idx=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(chk[i][j]==-1){
                z_cnt[idx++]=dfs(i,j);
            }
        }
    }
    
    for(int y=0;y<n;y++){
        for(int x=0;x<m;x++){
            if(M[y][x]!=1){
                continue;
            }
            set<int> s;
            for(int i=0;i<4;i++){
                int ny=y+y_l[i], nx=x+x_l[i];
                if(ny>=0 && ny<n && nx>=0 && nx<m){
                    if(chk[ny][nx]>0){
                        s.insert(chk[ny][nx]);
                    }
                }
            }
            for(auto i:s){
                M[y][x]+=z_cnt[i];
            }
            M[y][x]%=10;
        }
    }
        
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char c=M[i][j]+'0';
            cout<<c;
        }
        cout<<'\n';
    }
}

iron1209 4년 전 1

정말 어이없게도 입력받을때 char 받은것 그대로 배열에 저장해 큰 수를 더하려고 하니 오버 플로우가 난 것 같습니다.

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

문제

문제

출처

ICPC

메모리 초과...

iron1209 4년 전 0

iron1209 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말