글 읽기 - (소스첨부) 3055 탈출.. 오답이유를 모르겠습니다.

kons 8년 전 0

제 생각은 이렇습니다.

bfs로, Q[i][0]는 이전에 *였는지 S였는지. (S인경우 'a', '*'경우 'b'로 변환했습니다.)

Q[i][1]는 x좌표, Q[i[2]는 y좌표입니다.

s를 먼저 시행하는데, 'a'를 차지한 칸에 'b'로 변해있을 수 있어, if(trace!=D[x][y]) 인 조건에는 continue 시켰습니다.

이 후, 'a'인 경우 옆칸이 '.'일 경우 Q에 넣고, 그 칸을 'a' 로 변환. 'D'인 경우 해당 L을 출력 후 리턴.

'b'인 경우, 옆칸이 'a'이거나 '.'일때 Q에 넣고 그 칸을 'b'로 변환.

혹시 어느 부분이 틀렸는지 아시는분 도움 부탁드립니다.

#include<stdio.h>
#define INF 99999999
#define st 98
#define s 97
int N,M;
int result=INF;
int S[2],star[2];
char D[100][100];
int L[100][100];
int p[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int Q[3000][3]; // [0]: *인지 S인지, [1] x좌표, [2]y좌표.
void bfs();
void print(){
	printf("\n===================\n");
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			printf("%c",D[i][j]);
		}
		printf("\n");
	}
}
int main(void){

	scanf("%d %d",&N,&M);
	
	for(int i=0;i<N;i++){
		scanf("%s",&D[i]);
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(D[i][j]=='S'){S[0]=i; S[1]=j;}
			else if(D[i][j]=='*'){star[0]=i; star[1]=j;}
		}
	}
	Q[1][0] = s;
	Q[1][1] = S[0];
	Q[1][2] = S[1];
	D[S[0]][S[1]]=s;
	Q[2][0] = st;
	Q[2][1] = star[0];
	Q[2][2] = star[1];
	D[star[0]][star[1]]=st;
	bfs();
	if(result==INF){printf("KAKTUS\n");}
	else printf("%d\n",result);
	return 0;
}
void bfs(){
	int front=1;
	int rear=3;
	int x,y,trace ;

	while(front<=rear){
		trace = Q[front][0];
		x = Q[front][1];
		y = Q[front][2];
		front++;
		//print();
		if(trace!=D[x][y]){continue;}
		else{
			for(int i=0;i<4;i++){
				if(x+p[i][0]>=0 && x+p[i][0]<N && y+p[i][1]>=0 && y+p[i][1]<M &&
					D[x+p[i][0]][y+p[i][1]]!='X' && D[x+p[i][0]][y+p[i][1]]!=trace){
					if(trace==s && D[x+p[i][0]][y+p[i][1]]=='.'){
						D[x+p[i][0]][y+p[i][1]]=s;
						L[x+p[i][0]][y+p[i][1]] = L[x][y]+1;
						Q[rear][0]=trace;
						Q[rear][1]=x+p[i][0];
						Q[rear][2]=y+p[i][1];
						rear++;
					}
					else if(trace==st && (D[x+p[i][0]][y+p[i][1]]=='.'||D[x+p[i][0]][y+p[i][1]]==s)){
						D[x+p[i][0]][y+p[i][1]]=st;
						L[x+p[i][0]][y+p[i][1]] = L[x][y]+1;
						Q[rear][0]=trace;
						Q[rear][1]=x+p[i][0];
						Q[rear][2]=y+p[i][1];
						rear++;
					}
					else if(trace==s && D[x+p[i][0]][y+p[i][1]]=='D'){
						L[x+p[i][0]][y+p[i][1]] = L[x][y]+1;
						result = L[x][y]+1;
						return;
					}
				}
			}
		
		
		}
	}
}

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

문제

문제

출처

ICPC

(소스첨부) 3055 탈출.. 오답이유를 모르겠습니다.

kons 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말