글 읽기 - 50퍼에서 시간초과가 떠요 ㅠㅠ

ggodzxc123 6년 전 0

ㅠ_ㅠ 도와주시면 감사하겠습니다..

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
vector<pair<int,int>> F,M,E;
char G[1000][1000];
int dist,x,y;
void esc();
int main(){
	int T,i,u,v,j;
	char s[1000];
	scanf("%d",&T);
	while(T!=0){
		dist=0;
		scanf("%d %d",&y,&x);
		for(i=0;i<x;i++){
			scanf("%s",G[i]);
			for(j=0;j<y;j++){
                //불의 위치를 F에 넣습니다.
				if(*(G[i]+j)=='*'){
					F.push_back(make_pair(i,j));
				}
                //상근이의 위치를 M에 넣습니다.
				else if(*(G[i]+j)=='@'){
					M.push_back(make_pair(i,j));
				}
                //모서리에 있는 '.'들만 골라서 E에 넣습니다.
				else if(*(G[i]+j)=='.'){
					if(i==0 || i==x-1 || j==0 || j==y-1)
						E.push_back(make_pair(i,j));
				}
			}
		}
		esc();

		if(dist==-1)
			printf("IMPOSSIBLE\n");
		else
			printf("%d\n",dist);
		T--;
		F.clear();
		M.clear();
		E.clear();
	}
	return 0;
}



void esc(){
	int i,u,v,nf,nm,j;
	
	nf=(int)F.size();
	nm=(int)M.size();
	//종결조건
    //모서리의 '.'위치들만 모은 벡터를 검사
	for(i=0;i<(int)E.size();i++){
		if(G[E[i].first][E[i].second]=='@'){
            dist++;
            return;
        }
    }
    //움직일 상근이들의 위치가 없을때까지 모서리에 도달하지 못하면 -1
	if(M.empty()){
		dist=-1;
		return;
	}
	//진행
	//불 움직이기
	while(nf!=0){
		u=F[0].first;
		v=F[0].second;
		if((v!=y-1)&&(G[u][v+1]=='.' || G[u][v+1]=='@')){
			G[u][v+1]='*';
			F.push_back(make_pair(u,v+1));
		}
		else if((v!=0)&&(G[u][v-1]=='.' || G[u][v-1]=='@')){
			G[u][v-1]='*';
			F.push_back(make_pair(u,v-1));
		}
		if((u!=x-1)&&(G[u+1][v]=='.' || G[u+1][v]=='@')){
			G[u+1][v]='*';
			F.push_back(make_pair(u+1,v));
		}
		else if((u!=0)&&(G[u-1][v]=='.' || G[u-1][v]=='@')){
			G[u-1][v]='*';
			F.push_back(make_pair(u-1,v));
		}
		F.erase(F.begin());
		nf--;
	}


		

	//상근이 움직이기
	while(nm!=0){
		u=M[0].first;
		v=M[0].second;
		if((v!=y-1)&&(G[u][v+1]=='.')){
			G[u][v+1]='@';
			M.push_back(make_pair(u,v+1));
		}
		else if((v!=0)&&(G[u][v-1]=='.')){
			G[u][v-1]='@';
			M.push_back(make_pair(u,v-1));
		}
		if((u!=x-1)&&(G[u+1][v]=='.')){
			G[u+1][v]='@';
			M.push_back(make_pair(u+1,v));
		}
		else if((u!=0)&&(G[u-1][v]=='.')){
			G[u-1][v]='@';
			M.push_back(make_pair(u-1,v));
		}
		M.erase(M.begin());
		nm--;
	}
    
	//재귀함수
	dist++;
	esc();
}

kks227 6년 전 1

일단 G를 문자열로 받고 계시니까 G[1000][1001]로 한 칸 더 여유공간을 둬서 '\0' 문자를 넣어야 할 것 같습니다.

그와 별개로, 벡터의 erase 연산이 너무 많아서 시간초과가 나는 것 같은데

항상 F, M의 맨 뒤에만 새 원소를 삽입하고 맨 앞에서만 원소를 삭제하실 거라면, 그런 자료구조를 하나 찾아서 써보세요.

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

문제

문제

출처

ICPC

50퍼에서 시간초과가 떠요 ㅠㅠ

ggodzxc123 6년 전 0

kks227 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말