글 읽기 - 메모리 초과

flol47 3년 전 0

5%에서 메모리 초과가 뜨는데 뭐가 문제일까요
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
	int i,j;
	int c,r,p,q,t,x,y;
	int way_cnt[25000]={0,},water_cnt[25000]={0,};
	char maps[51][51];
	queue<pair<int,int> > way;
	queue<pair<int,int> > water;
	queue<int> way_time;
	queue<int> water_time;
    
	scanf("%d %d\n",&r,&c);
	for(i=0;i<r;i++) scanf("%s\n",maps[i]);
    
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
		{
        
			if(maps[i][j]=='S') //시작 지점 찾기
			{
				way.push(make_pair(i,j));
				way_cnt[0]++;
				way_time.push(0);
			}
            
			else if(maps[i][j]=='*') //물 찾기
			{
				water.push(make_pair(i,j));
				water_cnt[0]++;
				water_time.push(0);
			}
            
			else if(maps[i][j]=='D') //도착 지점 찾기
			{
				p=i;
				q=j;
			}
            
		}
	}
    
    if(water_time.size()==0) water_time.push(0); //물이 없을 경우
    
	while(1)
	{
    
		while(1) //물 퍼짐
		{
			
            t=water_time.front();
            
			if(water_cnt[t]<=0) break;
            
			x=water.front().first;
			y=water.front().second;
			water_cnt[t]--;
			water.pop();
			water_time.pop();
            
			if(x-1>=0&&maps[x-1][y]!='X'&&maps[x-1][y]!='D')
			{
				maps[x-1][y]='*';
				water.push(make_pair(x-1,y));
				water_time.push(t+1);
				water_cnt[t+1]++;
			}
            
			if(x+1<r&&maps[x+1][y]!='X'&&maps[x+1][y]!='D')
			{
				maps[x+1][y]='*';
				water.push(make_pair(x+1,y));
				water_time.push(t+1);
				water_cnt[t+1]++;
			}
            
			if(y-1>=0&&maps[x][y-1]!='X'&&maps[x][y-1]!='D')
			{
				maps[x][y-1]='*';
				water.push(make_pair(x,y-1));
				water_time.push(t+1);
				water_cnt[t+1]++;
			}
            
			if(y+1<c&&maps[x][y+1]!='X'&&maps[x][y+1]!='D')
			{
				maps[x][y+1]='*';
				water.push(make_pair(x,y+1));
				water_time.push(t+1);
				water_cnt[t+1]++;
			}
            
            if(water_cnt[t]<=0) break;
            
		}
        
		while(1) //길 찾기
		{
        
			if(way.empty())
			{
				printf("KAKTUS");
				return 0;
			}
            
			x=way.front().first;
			y=way.front().second;
			check[x][y]=true;
			t=way_time.front();
            
			if(x==p&&y==q)
			{
				printf("%d",t);
				return 0;
			}
            
			way_cnt[t]--;
			way.pop();
			way_time.pop();
            
			if(x-1>=0&&check[x-1][y]==false&&(maps[x-1][y]=='.'||maps[x-1][y]=='D'))
			{
			    check[x-1][y]=true;
				way.push(make_pair(x-1,y));
				way_time.push(t+1);
				way_cnt[t+1]++;
			}
            
			if(x+1<r&&check[x+1][y]==false&&(maps[x+1][y]=='.'||maps[x+1][y]=='D'))
			{
			    check[x+1][y]=true;
				way.push(make_pair(x+1,y));
				way_time.push(t+1);
				way_cnt[t+1]++;
			}
            
			if(y-1>=0&&check[x][y-1]==false&&(maps[x][y-1]=='.'||maps[x][y-1]=='D'))
			{
			    check[x][y-1]=true;
				way.push(make_pair(x,y-1));
				way_time.push(t+1);
				way_cnt[t+1]++;
			}
            
			if(y+1<c&&check[x][y+1]==false&&(maps[x][y+1]=='.'||maps[x][y+1]=='D'))
			{
			    check[x][y+1]=true;
				way.push(make_pair(x,y+1));
				way_time.push(t+1);
				way_cnt[t+1]++;
			}
            
			if(way_cnt[t]<=0) break;
            
		}
        
        /*
        확인용 출력
		for(i=0;i<r;i++)
		{
			for(j=0;j<c;j++) printf("%c",maps[i][j]);
			printf("\n");
		}
		printf("\n");
		*/
        
	}
	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

메모리 초과

flol47 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
