글 읽기 - 메모리초과 때문에 미치겠네요 ㅠㅠㅠ

taehoon_gwon 6년 전 0

메모리가 넘치는 것 같지도 않고, queue에 중복으로 들어가는 것 같지도 않은데 뭐가 문제일까요..

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,maxAreaSize,noWallMaxArea;
int area[51][51],binary[51][51];
vector<int>aSize;
queue<pair<int, int>>road;

//남동서북 
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

string checkWall(int bi){
    string res;
    while(bi!=1){
        char c;
        c=bi%2+'0';
        bi/=2;
        res+=c;
    }
    res+='1';
    for(unsigned long i=res.length();i<4;i++) {
        res+='0';
    }
    reverse(res.begin(), res.end());
    return res;
}

void checkArea(int x,int y,int areaCnt){
    road.push(make_pair(x, y));
    area[x][y]=areaCnt;
    
    int areaSize=0;
    while (!road.empty()) {
        int f=road.front().first;
        int s=road.front().second;
        
        areaSize++;
        
        string wall;
        wall=checkWall(binary[f][s]);
        
        //벽이 없는 곳의 좌표를 road에 넣기
        for(int i=0;i<4;i++) {
            if(wall[i]=='0'){
                if(area[f+dx[i]][s+dy[i]]==0){
                    area[f+dx[i]][s+dy[i]]=areaCnt;
                    road.push(make_pair(f+dx[i], s+dy[i]));
                }
            }
        }
        road.pop();
    }
    aSize.push_back(areaSize);
    //가장 큰 영역크기 비교
    if(areaSize>maxAreaSize){
        maxAreaSize=areaSize;
    }
}

int main(){
    cin>>n>>m;
    int b;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            cin>>b;
            binary[i][j]=b;
        }
    }
    int areaCnt=0;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            if(area[i][j]==0){
                areaCnt++;
                checkArea(i,j,areaCnt);
            }
        }
    }
    
    //벽 허물었을 때 최고 크기의 영역
    int noWallSize=0;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            for(int k=0;k<2;k++) {
                if(i+dx[k]>=1 && i+dx[k]<=m && j+dy[k]>=1 && j+dy[k]<=n){
                    if(area[i][j]!=area[i+dx[k]][j+dy[k]]){
                        noWallSize=aSize[area[i][j]-1]+aSize[area[i+dx[k]][j+dy[k]]-1];
                        if(noWallSize>noWallMaxArea){
                            noWallMaxArea=noWallSize;
                        }
                    }
                }
            }
        }
    }
    
//    for(int i=1;i<=m;i++) {
//        for(int j=1;j<=n;j++) {
//            printf("%d ",area[i][j]);
//        }
//        printf("\n");
//    }
//    printf("\n");
    
    printf("%d\n",areaCnt);
    printf("%d\n",maxAreaSize);
    printf("%d\n",noWallMaxArea);
}

sgchoi5 6년 전 0

http://gooddaytocode.blogspot....

대회에서 사용했던 tc 가 공개되어 있으니 한번 해보시길.... 다만 요 문제는 boj 오면서 마지막 답이 더 간단해졌습니다

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

문제

문제

출처

ICPC

메모리초과 때문에 미치겠네요 ㅠㅠㅠ

taehoon_gwon 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말