글 읽기 - 메모리 초과

gshs340507 5년 전 0

코드가 좀 길긴한데... 메모리 초과가 뜹니다. 큐에 너무많은 점이 들어가서 그런가요? 어떻게 해결해야 할지 모르겠습니다..

#include <bits/stdc++.h>
#define MAX 60
#define INF 987654321

using namespace std;
typedef pair <int, int> pii;

// empty : 0, water : 1, rock : 2, beaver : 3, gosum : 4
int forest[MAX][MAX];
int memo[MAX][MAX];
int row, col;
int bfs1[4] = {1, -1, 0, 0};
int bfs2[4] = {0, 0, 1, -1};

int BFS();

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> row >> col;
    for(int i = 1; i <= row; i++){
        string S;
        cin >> S;
        for(int j = 1; j <= col; j++){
            if(S[j - 1] == '.') forest[i][j] = 0;
            else if(S[j - 1] == '*') forest[i][j] = 1;
            else if(S[j - 1] == 'X') forest[i][j] = 2;
            else if(S[j - 1] == 'D') forest[i][j] = 3;
            else forest[i][j] = 4;
        }    
    }
    int res = BFS();
    if(res == INF) cout << "KAKTUS";
    else cout << res;
}

int BFS()
{
    queue <pii> Q, W;
    int ret = -1, Wsize = 0;
    for(int i = 1; i <= row; i++){
        for(int j = 1; j <= col; j++){
            if(forest[i][j] == 1){
                W.push(make_pair(i, j));
                memo[i][j] = INF;
                Wsize++;
            }
            if(forest[i][j] == 4)
                Q.push(make_pair(i, j));
        }
    }
    while(!Q.empty()){
        int R1 = Q.front().first;
        int C1 = Q.front().second;
        Q.pop();
        if(forest[R1][C1] == 3) return ret + 1;
        if(memo[R1][C1] == ret + 1){
            ret++;
            int sub = 0;
            while(Wsize--){
                int R3 = W.front().first;
                int C3 = W.front().second;
                W.pop();
                for(int i = 0; i < 4; i++){
                    int R4 = R3 + bfs1[i];
                    int C4 = C3 + bfs2[i];
                    if(R4 <= 0 || C4 <= 0 || R4 > row || C4 > col) continue;
                    if(forest[R4][C4] == 2 || memo[R4][C4] == INF || forest[R4][C4] == 3) continue;
                    W.push(make_pair(R4, C4));
                    memo[R4][C4] = INF; sub++;
                }        
            }
            Wsize = sub;        
        }
        
        for(int i = 0; i < 4; i++){
            int R2 = R1 + bfs1[i];
            int C2 = C1 + bfs2[i];
            if(R2 <= 0 || C2 <= 0 || R2 > row || C2 > col) continue;
            if(memo[R2][C2] == INF) continue;      
            Q.push(make_pair(R2, C2));
            memo[R2][C2] = memo[R1][C1] + 1;  
        }
    }
    return INF;
}

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

문제

문제

출처

ICPC

메모리 초과

gshs340507 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말