글 읽기 - ideone 에서 통과하나 여기서 런타임 오류...

leejun332211 5년 전 1

안녕하세요 오늘도 질문을 드립니다.
ideone 에서 돌아가고 시간도 0s안에 끝나는데.... 런타임오류가 뜹니다...
왜그런지 같이 알아갈수 있을까요?
질문도 다찾아보고 큐도 충분히 늘려보고 혹시 안돌렸다고 말씀하실까봐....
캡쳐도 올립니다... 감사합니다

#include <stdio.h>


int n,m; // n m
char map[200][200];
int qu[9][40000];		//0 n 1 m 2 length 3 a 4 b 5 c 6 d 7 e 8 f
int pos, cnt;
int result=1;

void enqu(int a,int b, int c, int d, int e, int f, int g, int h, int i){

	int ppp;
	qu[0][cnt]=a;
	qu[1][cnt]=b;
	qu[2][cnt]=c;
	qu[3][cnt]=d;
	qu[4][cnt]=e;
	qu[5][cnt]=f;
	qu[6][cnt]=g;
	qu[7][cnt]=h;
	qu[8][cnt]=i;



//	int j;
//	for(j=0;j<9;j++){
//	printf("%d ",qu[j][cnt]);
//	}
//	printf("%d\n",cnt);

	cnt++;
	
	
}


void bfs(int a, int b,int tt1,int tt2){
	int i,j,k;
	int a1,a2,a3,a4,a5,a6;
	int pp;
	enqu(a,b,0,0,0,0,0,0,0);
	
	while(pos<cnt){
		i=qu[0][pos];
		j=qu[1][pos];
		k=qu[2][pos];
		a1=qu[3][pos];
		a2=qu[4][pos];
		a3=qu[5][pos];
		a4=qu[6][pos];
		a5=qu[7][pos];
		a6=qu[8][pos];

		//printf("%d %d %d %d %d %d %d %d %d %d\n",pos,i,j,k,a1,a2,a3,a4,a5,a6);	

		
		if(i>0&&map[i-1][j]!='#'){		//up

			if(map[i-1][j]>='A'&&map[i-1][j]<='F'){
				pp=map[i-1][j]-'A'+3;
				if(qu[pp][pos]>0){
					if(pp==3)					
					enqu(i-1,j,k+1,a1-1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i-1,j,k+1,a1,a2-1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i-1,j,k+1,a1,a2,a3-1,a4,a5,a6);
					if(pp==6)					
					enqu(i-1,j,k+1,a1,a2,a3,a4-1,a5,a6);
					if(pp==7)					
					enqu(i-1,j,k+1,a1,a2,a3,a4,a5-1,a6);
					if(pp==8)					
					enqu(i-1,j,k+1,a1,a2,a3,a4,a5,a6-1);
				}
			}
			else if(map[i-1][j]>='a'&&map[i-1][j]<='f'){
					pp=map[i-1][j]-'a'+3;
					if(pp==3)					
					enqu(i-1,j,k+1,a1+1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i-1,j,k+1,a1,a2+1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i-1,j,k+1,a1,a2,a3+1,a4,a5,a6);
					if(pp==6)					
					enqu(i-1,j,k+1,a1,a2,a3,a4+1,a5,a6);
					if(pp==7)					
					enqu(i-1,j,k+1,a1,a2,a3,a4,a5+1,a6);
					if(pp==8)					
					enqu(i-1,j,k+1,a1,a2,a3,a4,a5,a6+1);

			}
			else{
				enqu(i-1,j,k+1,a1,a2,a3,a4,a5,a6);
			}
		}
		
		
		if(i<n-1&&map[i+1][j]!='#'){		//down
			if(map[i+1][j]>='A'&&map[i+1][j]<='F'){
				pp=map[i+1][j]-'A'+3;
				if(qu[pp][pos]>0){
					if(pp==3)					
					enqu(i,j+1,k+1,a1-1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i,j+1,k+1,a1,a2-1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i,j+1,k+1,a1,a2,a3-1,a4,a5,a6);
					if(pp==6)					
					enqu(i,j+1,k+1,a1,a2,a3,a4-1,a5,a6);
					if(pp==7)					
					enqu(i,j+1,k+1,a1,a2,a3,a4,a5-1,a6);
					if(pp==8)					
					enqu(i,j+1,k+1,a1,a2,a3,a4,a5,a6-1);

				}
			}
			else if(map[i+1][j]>='a'&&map[i+1][j]<='f'){
					pp=map[i+1][j]-'a'+3;					
					if(pp==3)					
					enqu(i+1,j,k+1,a1+1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i+1,j,k+1,a1,a2+1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i+1,j,k+1,a1,a2,a3+1,a4,a5,a6);
					if(pp==6)					
					enqu(i+1,j,k+1,a1,a2,a3,a4+1,a5,a6);
					if(pp==7)					
					enqu(i+1,j,k+1,a1,a2,a3,a4,a5+1,a6);
					if(pp==8)					
					enqu(i+1,j,k+1,a1,a2,a3,a4,a5,a6+1);
			}
			else{
				enqu(i+1,j,k+1,a1,a2,a3,a4,a5,a6);
			}
		}
		
		if(j>0&&map[i][j-1]!='#'){		//left
			if(map[i][j-1]>='A'&&map[i][j-1]<='F'){
				pp=map[i][j-1]-'A'+3;
				if(qu[pp][pos]>0){
					if(pp==3)					
					enqu(i,j-1,k+1,a1-1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i,j-1,k+1,a1,a2-1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i,j-1,k+1,a1,a2,a3-1,a4,a5,a6);
					if(pp==6)					
					enqu(i,j-1,k+1,a1,a2,a3,a4-1,a5,a6);
					if(pp==7)					
					enqu(i,j-1,k+1,a1,a2,a3,a4,a5-1,a6);
					if(pp==8)					
					enqu(i,j-1,k+1,a1,a2,a3,a4,a5,a6-1);

				}
			}
			else if(map[i][j-1]>='a'&&map[i][j-1]<='f'){
				pp=map[i][j-1]-'a'+3;
				if(pp==3)					
					enqu(i,j-1,k+1,a1+1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i,j-1,k+1,a1,a2+1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i,j-1,k+1,a1,a2,a3+1,a4,a5,a6);
					if(pp==6)					
					enqu(i,j-1,k+1,a1,a2,a3,a4+1,a5,a6);
					if(pp==7)					
					enqu(i,j-1,k+1,a1,a2,a3,a4,a5+1,a6);
					if(pp==8){					
					enqu(i,j-1,k+1,a1,a2,a3,a4,a5,a6+1);
//					printf("1\n");
					}
				}			
			else{
				enqu(i,j-1,k+1,a1,a2,a3,a4,a5,a6);
//					printf("2\n");
			}
		
		}
		if(j<m-1&&map[i][j+1]!='#'){		//right
			if(map[i][j+1]>='A'&&map[i][j+1]<='F'){
				pp=map[i][j+1]-'A'+3;
				if(qu[pp][pos]>0){
					if(pp==3)					
					enqu(i,j+1,k+1,a1-1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i,j+1,k+1,a1,a2-1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i,j+1,k+1,a1,a2,a3-1,a4,a5,a6);
					if(pp==6)					
					enqu(i,j+1,k+1,a1,a2,a3,a4-1,a5,a6);
					if(pp==7)					
					enqu(i,j+1,k+1,a1,a2,a3,a4,a5-1,a6);
					if(pp==8)					
					enqu(i,j+1,k+1,a1,a2,a3,a4,a5,a6-1);

				}
			}
			else if(map[i][j+1]>='a'&&map[i][j+1]<='f'){
					pp=map[i][j+1]-'a'+3;	
					if(pp==3)					
					enqu(i,j+1,k+1,a1+1,a2,a3,a4,a5,a6);
					if(pp==4)					
					enqu(i,j+1,k+1,a1,a2+1,a3,a4,a5,a6);
					if(pp==5)					
					enqu(i,j+1,k+1,a1,a2,a3+1,a4,a5,a6);
					if(pp==6)					
					enqu(i,j+1,k+1,a1,a2,a3,a4+1,a5,a6);
					if(pp==7)					
					enqu(i,j+1,k+1,a1,a2,a3,a4,a5+1,a6);
					if(pp==8){					
					enqu(i,j+1,k+1,a1,a2,a3,a4,a5,a6+1);
//					printf("3\n");
					}
				}
			
			else{
				enqu(i,j+1,k+1,a1,a2,a3,a4,a5,a6);
//				printf("4\n");
			}
		}
		
		if(i==tt1&&j==tt2){
			result=0;
			break;
		}
		
		pos++;	
	}
}


int main(){

	int i,j;
	int x,y;
	int tt1,tt2;
	char pp[51];
	
	scanf("%d %d",&n,&m);
	
	for(i=0;i<n;i++){
		scanf("%s",map[i]);
		for(j=0;j<m;j++){
			if(map[i][j]=='0'){
				x=i;
				y=j;
			}
			else if(map[i][j]=='1'){
				tt1=i;
				tt2=j;
			}
		}
	}
	
	bfs(x,y,tt1,tt2);
	
	if(result==0){
	printf("%d",qu[2][pos]);
	}
	else if(result==1){
	printf("-1");
	}
	
	return 0;
}

chogahui05 5년 전 0

어떤 알고리즘으로 접근하신건지는 안 말해주셔도 되고요.

상태 정의만 말해 주세요. 어떠한 상태를 어떻게 정의했는지.

ex. 상태1 = x축, 상태2 = y축 위치로 정의하였습니다.

leejun332211 5년 전 0

n 가로, m 세로, map : 맵 qu[9][]=> 0부터 x축,y축,길이누적,a먹은거,b먹은거,....,f먹은거

result 1로 끝나면 잘끝나서 길이구한거
reuslt 0 이면 다돌았으나 못구해서 -1 출력
입니다...!!

chogahui05 5년 전 0

일단. 이거 답이 -1은 아닐 거 같은데..

4 7
f0aF...
#####bA
######.
1.....B

chogahui05 5년 전 0

일단 상태가 x축 y축은 들어가니까..

그 다음이 문제인 건데.. 일단 하나 궁금한 건. qu[9][40000]이 뭘 의마하나요? 아. 보니까 이거네요.

qu[aa][bb]라고 하면 bb는 이동 거리고 aa는 상태들 나타낼려고 하는 것이지요? 대충 상태가 9개 정도 될 거니까..

chogahui05 5년 전 1

문제는 바로 보이네요. visit 체크를 안 하다 보니까 Queue에 엄청나게 들어가고

결국 메모리 초과로 이어지네요. 상태 정의는 얼추 맞았으니까.

어떤 식으로 처리할 건지만 고민해 보세요. 어떻게 이미 방문한 상태를 체크할 건지.

kmn4555 3년 전 0

1년 후에도 도움받고 갑니다~ 아래 케이스 통과했는데 이게 안됐네요 ㅎㅎ

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

문제

문제

출처

ICPC

ideone 에서 통과하나 여기서 런타임 오류...

leejun332211 5년 전 1

chogahui05 5년 전 0

leejun332211 5년 전 0

chogahui05 5년 전 0

chogahui05 5년 전 0

chogahui05 5년 전 1

kmn4555 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말